BOJ. 1931

#BOJ1931

회의실 배정

문제를 처음 보고 나서 그리디를 사용해야 한다는 감은 왔지만 정확히 어떤 부분에서 어떻게 그리디를 사용해야 할지 감이 오지 않았었다. 전학영 시간이 끝나고 학식을 먹고 있는데 시작시간이 아닌 끝 시간을 기준으로 정렬을 한다면 될거라는 생각이 들었다. 하루키 수업 시간 시작과 동시에 코드를 만들기 시작해서 완성해서 돌렸는데 화가나게도 시간초과가 나오고 있다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
   return a.second < b.second;
}

int main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(NULL);
   int N, cnt = 0, index = 0, error = 0;
   cin >> N;
   vector< pair<int, int> > v(N);
   for (int i = 0; i < N; i++){
       cin >> v[i].first >> v[i].second;
   }
   sort(v.begin(), v.end(), compare);
   while(error != 1){
       for(int i = index; i < N; i++){
           if (v[index].second <= v[i].first){
               index = i;
               cnt ++;
               break;
           }
           if (i == N - 1){
               error = 1;
           }
       }
   }
   cout << cnt + 1;
}

빅오를 고민해보자. 최악의 케이스는 N^2인거 같다. 그렇다면 이걸 해결하려면 어떤 부분을 해결해줘야 할까? 과감하게 while문을 없애고 하나의 for문으로 고쳐야겠다는 생각이 들었다. 그렇게 과감하게 에러 찾는 과정과 같은 불필요한 부분들을 빼고 N이 될 수 있도록 코드를 수정하였다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    return a.second < b.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, cnt = 1;
    cin >> N;
    vector< pair<int, int> > v(N);
    for (int i = 0; i < N; i++){
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), compare);
    int index = v[0].second;
    for (int i = 1; i < N; i++){
        if (index <= v[i].first){
            cnt ++;
            index = v[i].second;
        }
    }
    cout << cnt;
}

빠르게 채점 되는 속도에 당연히 맞을 줄 알았지만 현실은 88프로에서 "틀렸습니다" 였다. 그래서 질문게시판을 가고 있었는데 같은 문제를 마주한 사람을 발견하였다. 생각해보니 종료시점이 같을 경우에 시작시간이 이른 것을 선택해야만 했던 것이다. 왜냐하면 시작시간과 종료시점이 같은 경우에는 이 문제의 정답이 다르게 출력 될 수 있었던 것이다! 이 부분을 해결하고 고대하던 "맞았습니다"를 받을 수 있었다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b){
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, cnt = 1;
    cin >> N;
    vector< pair<int, int> > v(N);
    for (int i = 0; i < N; i++){
        cin >> v[i].first >> v[i].second;
    }
    sort(v.begin(), v.end(), compare);
    int index = v[0].second;
    for (int i = 1; i < N; i++){
        if (index <= v[i].first){
            cnt ++;
            index = v[i].second;
        }
    }
    cout << cnt;
}

그나저나 이게 진짜 몇트만의 정답인 것이냐... 내 정답률...ㅜㅜ