[코드트리] 서로 다른 구간의 수

코드트리 문제 : https://www.codetree.ai/missions/8/problems/number-of-distinct-segments?&utm_source=clipboard&utm_medium=text 

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

 

이전에 올린 문제와 상당히 유사하며, 코드를 이어서 조금의 변형만 하면 된다.

문제 설명 : 

 이전 문제와는 다른 것은 선분을 합친다는 것이다. 선분이 겹치는 부분이 있다면 하나의 선분으로 합쳐져서 시작점과 끝점이 변경되게 된다. 그렇게 선분들의 범위를 깡그리 겹치고, 그렇게 합친 후의 선분의 개수를 찾으면 된다.

 

 물론, 여기서는 그렇게 선분을 합치는 과정을 쓰지 않고, +1,-1 테크닉을 응용하여 문제를 해결한다.

 

https://hajm0702.tistory.com/42

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

 

여기도 +1,-1 테크닉을 이용하긴 한다.

 

#include <iostream>
#include <vector>
#include <utility>
#include <unordered_set>
#include <tuple>
#include <algorithm>

using namespace std;

int main() {
    int section_num;
    cin >> section_num; //구간 몇 개인지.
    int x1,x2; //좌표 임시저장.
    pair<int, int > section[section_num];
    vector<tuple<int,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_tuple(x1,+1,input_cnt)); //시작부분에는 +1이라는 가중치를
        chcekSec.push_back(make_tuple(x2,-1,input_cnt));//끝나는 부분에는 -1이라는 가중치를 주어 선분의 개수를 알 수 있도록 한다.
    }
    sort(chcekSec.begin(),chcekSec.end());

    int ans=0;
    int index;
    int Maxsum=0;

    unordered_set<int> segs;//선분을 넣는 집합.

    for(int input_cnt=0; input_cnt <section_num * 2;input_cnt++){//section_num*2 하는 이유는 구간 별로 점이 2개씩 주어지게 되니까.
        tie(x1,x2,index)=chcekSec[input_cnt];//여기서 x1은 좌표, x2는 +1인지 -1인지 그 좌표에 해당하는 값을 넣는다.
        
        if(x2==+1){
            if((int)segs.size()==0){ //남는 선분이 없으니까 새로운 구간이 나타났다는 뜻이다.
                ans++;
            }
            segs.insert(index);
        }else{
            segs.erase(index); //집합에서 선분 지우기.
        }
    }

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

여기선 구간의 정보를 이용해서 선분을 구분해야 한다. 선분의 번호를 집합에 넣는다. 이 집합을 어떻게 사용하느냐

 

for문으로 좌표를 순회하면서 좌표가 시작점인지 끝점인지 확인한다. 즉, +1을 만나면 집합에 선분을(index 변수가 선분의 번호이다.) 넣어둔다. 선분을 기억하는 것이다. 그리고 -1을 만나면 그 선분을 집합에서 빼둔다.

 

그런데 여기서 집합의 원소 개수가 0일 경우 새로운 구간을 만나게 되는 것이니까 서로 다른 구간의 수를 저장하는 변수 ans에 +1을 한다.

 

이런 방식으로 선분을 합치는 과정을 제외하고 서로 다른 구간을 찾아낼 수 있는 것이다.

 

코드 검증.

section_num에는 구간이 몇 개인지(선분이 몇 개인지) 입력받아 넣는다.

x1,x2에는 선분의 시작점과 끝점의 좌표를 받아서 section이라는 pair 원소를 담는 배열에 넣는다. 이후 tuple을 원소로 담는 벡터 checkSec을 이용한다. tuple에는 해당 좌표, 해당 좌표가 시작점인지 끝점인지, 선분의 번호를 담는다.

 

시작점인지 끝점인지는 가중치 +1,-1로 구분할 수 있는 것이다.

 

이후 벡터를 정렬하고. 정렬되지 않은 집합인 segs에는 선분을 기억할 수 있도록 한다.(담는다는 뜻.)

 

for문을 통해서 tie()를 이용해서 벡터의 원소인 tuple의 값을 각 변수에 넣는다. 이후 시작점이면 선분을 집합에 넣고, 만약 집합에 아무것도 없었다면 새로운 구간이라는 뜻이므로 서로 다른 구간의 수를 저장하는 ans를 +1 한다. 끝점이면 해당 선분을 집합에서 제외한다.

 

 선분의 개수를 통해서 겹쳐진 이후를 생각할 수 있다. 굳이 합칠 필요 없어서 좋다. 

 

선분의 개수가 0인 상태에서 시작점이면 왜 ans가 늘어나는지 생각하는 것이 중요하다. 이것만 이해하면 이 코드의 중요부분, 발상을 이해할 수 있다.