boj 2170번 문제를 통해 또다시 접하게된 시작과 끝점을 따로 구분지어줘서 push_back 해준뒤에 정렬해서 각각의 값을 활용하는 방법.

이번 문제도 11000 문제처럼 각각의 시작점과 끝점에 시작점의 경우 +1과 엮어서, 끝점의 경우 -1과 엮어서 pair로 vector에 넣고, 그걸 sort해서 정렬되어있는 형태의 값을 이용해서 현재 중첩되어 있는 것이 있는지를 +1한 값, -1한 값들을 cnt 변수에 저장하면서 사용하는 형태의 문제였다. 

내가 제출해서 맞은 풀이법과는 조금 다른데, 이러한 풀이법에 익숙해지면 이런 문제에서 현재 중첩으로 이루어지고 있는 상태가 있는지에 대해서 알아보기 쉽게 사용할 수 있을것 같아서 다시 한번 정리한다. 

 

결국 핵심인 부분은, 

while(n--){
        int l, r;
        cin>>l>>r;
        events.push_back({l,1});
        events.push_back({r,-1});
    }

이러한 형태로 좌표의 시작점, 그리고 좌표의 끝점을 각각 따로 나누어서 시작은 +1, 끝은 -1과 pair로 받아서 push_back해주는 것이다. 

이걸 이제 while 다 끝내고 나서 나온 상황에서 sort로 싹 돌려주면

예를들어 

4
1 3
2 5
3 5
6 7

와 같은 상황으로 입력이 주어지면 sort를 돌렸을때의 상황은 

1 1
2 1
3 -1
3 1
5 -1
5 -1
6 1
7 -1

로 나오게 된다. 

그럼 이 값들을 이용해서 지금 보고 있는 값이 시작점의 값인지, 끝점의 값인지를 +1, -1을 이용해서 알수 있고, 그리고 같은 값의 경우 sort에서 두번째 인자인 -1이 먼저 앞서게 되어서(기본 sort시에) 결국 끝나는 점에 대해서 원하는 연산을 먼저 처리하게 된다. 

이러한 표현 법에 대해서 더욱 더 익숙해지고 이렇게 겹쳐지는 형태의 강의실의 사용이던지, 선을 긋는다던지, 시간이 겹친다던지 하는 형태의 문제에서 잘 활용해보도록 하자.