백준 1931 회의실 배정-greedy algorithm(C++)

https://www.acmicpc.net/problem/1931

1931번: 회의실배정

그리디 알고리즘의 전형적인 예시이다. 학교 알고리즘 시간에 거의 똑같은 문제를 다뤄봐서 쉽게 풀줄 알았는데,

막상 어려웠던 부분은 구현단계였다.

 

우선 문제를 풀기 위해서는 끝나는 시간에 주목해야한다.

1.끝나는 시간이 가장 빠른 녀석을 골라서,

2.그 끝나는 시간보다 시작시간이 빠른 녀석들을 골라

3.그 녀석들을 전부 지우고,

1~3의 과정을 반복하는 식이다.

 

시작시간과 끝시간을 배열로 넣어서 그걸 다시 벡터로 저장한 다음에,

벡터를 끝 시간을 기준으로 오름차순으로 정렬해야한다.

(pair를 가진 벡터는, 정렬하고자 하는 부분을 앞쪽으로 배치시켜야 원하는 대로 오름차순 정렬이 가능하더라고.)

 

그 후에 while문을 통해서 벡터가 빌때까지 코드를 돌리려고 했지만,, 실패했다.

시간초과가 떠버렸다...

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int cBegin[100000], cEnd[100000];
 
int schedule()
{
    vector<pair<int,int>> meeting;
    for(int i=0; i<N; i++){
        meeting.push_back(make_pair(cEnd[i],cBegin[i]));
    }
    sort(meeting.begin(),meeting.end());
    reverse(meeting.begin(),meeting.end());
 
    int answer=0;
    while(meeting.size()){
        int min_endtime = meeting[meeting.size()-1].first;
//        cout<<meeting.size()-1;
        meeting.erase(meeting.begin()+meeting.size()-1);
//        cout<<min_endtime<<" while statemnet start!!!\n";
            for(int i=0; i<meeting.size(); i++)
            {
//                cout<<meeting[i].second<<"\n";
//              cout << meeting[i].second << "\n";   //first가 끝나는시간, second가 시작시간
                if(meeting[i].second<min_endtime) {
//                    cout << meeting[i].second << "will be erased\n";
                    meeting.erase(meeting.begin() + i);
                    i--;
                }
            }
            answer++;
        }
    return answer;
}
 
 
int main(void)
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> cBegin[i] >> cEnd[i];
    cout << schedule() << endl;
    return 0;
 
}

어떻게 바꿔야할지 방식을 고민하다가, AC받은 코드를 읽어봤는데,

그냥 변수에다가 cashing을 함으로써 다음과 같이 효율적으로 코드를 작성할 수 있었다.

이런거 생각해내는게 참 코드짜는 실력인 것 같다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int N;
int cBegin[100000], cEnd[100000];
 
int schedule()
{
    vector<pair<int,int>> meeting;
    for(int i=0; i<N; i++){
        meeting.push_back(make_pair(cEnd[i],cBegin[i]));
    }
    sort(meeting.begin(),meeting.end());
 
    int answer=0;
    int earlist=0;
    for(int i=0; i<N; i++){
        int begin_time=meeting[i].second, end_time=meeting[i].first;
        if(earlist<=begin_time){
            earlist = end_time;
            answer++;
        }
    }
    return answer;
}
 
 
int main(void)
{
    cin >> N;
    for (int i = 0; i < N; i++)
        cin >> cBegin[i] >> cEnd[i];
    cout << schedule() << endl;
    return 0;
 
}