[코드트리] 가장 많이 겹치는 구간

코드트리 문제 : https://www.codetree.ai/missions/8/problems/section-with-maximum-overlap?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 설명 :

 먼저 입력으로 선분 몇 개가 주어지는지 받고, 그 다음 줄부터는 선분의 시작점과 끝점에 대한 정보가 주어지게 된다. 선분끼리의 점은 중복으로 주어지지는 않는다고 가정해도 좋다.

 

 그렇게 선분이 제일 많이 겹치는 구간을 찾아 얼마나 겹쳐져 있는지 그 수를 출력하면 된다.

 

 

문제 해결 방식은 다음과 같다.

+1,-1 테크닉을 사용했다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm> //sort
#include <tuple> // tie

using namespace std;

int main() {
    int section_num;
    cin >> section_num; //구간 몇 개인지.
    int x1,x2; //좌표 임시저장.
    pair<int, int > section[section_num];
    vector<pair<int,int>> chcekSec;
    //구간 정보 받기.
    for(int input_cnt=0; input_cnt <section_num;input_cnt++){
        cin >> x1 >> x2;
        section[input_cnt]=make_pair(x1,x2);
        //section[input_cnt].first=x1; 두 방식 다 가능하다.
        //section[input_cnt].second=x2;
    }
    for(int input_cnt=0;input_cnt<section_num;input_cnt++){
        tie(x1,x2)=section[input_cnt]; //section 배열에 있는 페어 원소의 값을 x1,x2 에 넣는다.
        chcekSec.push_back(make_pair(x1,+1)); //시작부분에는 +1이라는 가중치를
        chcekSec.push_back(make_pair(x2,-1));//끝나는 부분에는 -1이라는 가중치를 주어 선분의 개수를 알 수 있도록 한다.
    }
    sort(chcekSec.begin(),chcekSec.end());

    int sum=0;
    int Maxsum=0;

    for(int input_cnt=0; input_cnt <section_num * 2;input_cnt++){//section_num*2 하는 이유는 구간 별로 점이 2개씩 주어지게 되니까.
        tie(x1,x2)=chcekSec[input_cnt];//여기서 x1은 좌표, x2는 +1인지 -1인지 그 좌표에 해당하는 값을 넣는다.
        
        sum += x2;
        Maxsum=max(Maxsum,sum);
        
    }

    cout << Maxsum <<'\n';
    return 0;
}

 페어의 배열은 구간의 정보(시작점과 끝점)

페어를 받는 벡터 checkSec 은 시작점 좌표에는 +1, 끝점 좌표에는 -1을 페어로 넣어준다.

 

 이후 for문 반복문을 통해서 x1,x2는 메모리 덜 쓸라구 다시 재사용하는 것이다. x1은 여기서 벡터 checkSec에서 가져온 좌표를 꺼내오고, x2는 +1,-1인지 그 정보가 들어가서, sum에는 겹친 선분의 개수를 넣는 것이고 그것을 x2에 넣어주는 것이다.