boj 11000번 문제를 통해서 접하게된 vector에 시작 인자와 끝 인자를 구분해서 담는 기술에 관하여.

일단 boj 11000번 문제의 경우 시작 숫자와 끝 숫자를 구분지어주어야 문제를 푸는데 도움이 되는 상황인데, 이때에 내가 접한 정답 코드에서는 vector를 활용하여서 시작 숫자와 끝 숫자를 구분하여서 vector에 저장하고, 그것을 sort를 통해서 정렬했을때 만약 시작과 끝이 같은 숫자인 경우 끝이 먼저, 그리고 시작이 다음에 나오게 만드는데, 그 방법으로 끝 숫자를 pair로 -1을 함께, 그리고 시작 숫자의 경우 pair로 1을 함께 묶어서 push_back을 해놓는다. 

그와 같은 방법에 대해서 익숙하지 않아서 떠올리지 못했는데, 그 정답 코드의 중간부분까지 진행하고 과연 sort를 진행했을때 어떤식으로 나오는지에 대해서 작성해보겠다. 

 

#include <bits/stdc++.h>
using namespace std;

int n;
vector<pair<int,int>> event;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=0; i<n; i++){
        int s, t;
        cin>>s>>t;
        event.push_back({s,1});
        event.push_back({t,-1});//-1로 두번째 인자를 만들어서 t를 넣었기 때문에, 정렬을 했을때 만약 s=3인 경우와, t=3인 경우가 있을때, t=3인 경우가 더 먼저 놓이고 그 다음에 s=3인 경우가 놓이게 된다(기본정렬 오름차순으로 했을시에)
    }
    sort(event.begin(),event.end());
    cout<<'\n';
    for(auto c: event)
        cout<<c.first<<' '<<c.second<<'\n';
}
/*
문제의 답은 결국 가장 많은 수업이 열리는 시간에서의 수업의 개수.
수업 개수의 변화가 발생하는 (s,1),(t,-1)을 전부 수집한 후 정렬하고 같은 시간대의 event를
묶어서 처리한다. 
*/

 

일단 이 코드는 중간부분에 시작의 경우 1과 함께 pair로, 끝의 경우 -1과 함께 pair로 push_back을 했을때의 그 vector event를 sort했을때 어떻게 보여지는지 알아보기 위해서 작성했다. 

이때에 예시 입력으로 주어진 값들을 넣어보고 sort를 시행한뒤에 출력을 해보면, 

 

이러한 값들을 얻을 수 있다. 

결국 입력으로 주어진 값들에서 시작값과 끝나는 값을 쭉 일렬로 나열하는데, 그때에 sort를 기본으로 사용해서 오름차순 정렬을 진행하고, 그렇게 진행했을때 시작값과 끝값의 숫자가 같아지는경우 끝값이 먼저 나오도록 -1을 끝값과 함께 pair로 묶었기 때문에, 시작값과 끝값이 같아지는 경우 두번째 인자인 -1,1 의 순서로 오름차순 정렬 되기 때문에 -1과 함께 엮은 끝값이 더 먼저 나오게 된다.

그래서 이렇게 구분을 지어서 쭉 일렬로 값을 나열 할 수 있고, 끝값을 먼저 나타낼 수 있는 것이다.

 

이러한 형태의 표현을 익숙하게 사용할 수 있도록 충분하게 익히도록 하자. 지금 그리디 문제를 풀때, 이런식의 sort를 활용하는데 있어서 컨테이너를, 특히 자주 접하게 되는 vector에 pair 혹은 tuple을 활용해서 인자를 넣을때 원하는 형태로 sort를 하는데 사용할만한 잡기술들을 접하게 되는데, 아직 이러한 잡기술들이 익숙하지 않다. 익숙해지도록 하자.