BaekJoon 1931 문제에서..

BaekJoon 1931 회의실 배정 문제

https://alsrudwls.tistory.com/18

 

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

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list;

    for (int i = 0; i < n; i++)
    {
        int start, end;
        cin >> start >> end;
        list.push_back(make_pair(end, start));
    }
    sort(list.begin(), list.end());

    int time = list[0].first;
    int count = 1;
    for (int i = 1; i < n; i++)
    {
        if (list[i].second >= time)
        {
            count++;
            time = list[i].first;
        }
    }
    cout << count;
}

이 문제에서 start, end 순으로 입력을 받았는데, list에 end, start로 저장하는게 뒤에 코드를 작성하는데 헷갈려

마음에 들지 않았다.

 

그래서 코드를 조금 변형시켜 입력받은 그대로 저장해보기로 했다.

다음은 변형한 코드이다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

//second 값을 비교하여 오름차순으로 정렬, compare 함수 없이 sort 정렬 시 first 값을 기준으로 정렬함
bool compare(const pair<int, int>& a, const pair<int, int>& b)
{
    return a.second < b.second;
}

int main()
{
    int n;
    cin >> n;
    vector<pair<int, int>> list;

    for (int i = 0; i < n; i++)
    {
        int start, end;
        cin >> start >> end;
        list.push_back(make_pair(start, end));
    }

    sort(list.begin(), list.end(),compare);
    
    //출력값 테스트
    for (const auto& it : list)
    {
        cout << "회의 시작 시간 : " << it.first << " "<< "회의 종료 시간: " << it.second << "\n";
    }
    
    //처음 시작 시간을 제일 첫번째 끝나는 회의시간으로 하고 
    int time = list[0].second; 
    //1을 카운트한다. 
    int count = 1;
    for (int i = 1; i < n; i++)
    {
        //현재 시간(Time)이 다음 회의 시작 시간과 똑같거나 클 때,
        if (list[i].first >= time)
        {
            //카운트를 증가시키고,
            count++;
            //현재 시간을 회의 종료 시간으로 지정한다. 
            time = list[i].second;
        }
    }
    cout << count << "\n";
    return 0;
}

second 값을 비교하여 끝나는 시간을 기준으로 정렬하고, 그 아래 코드도 끝나는 시간을 기준으로 알고리즘이 작동하도록

코드를 변형해주었다. 

수정된 코드 정렬 출력값

 

입력 자체가 종료시간에 맞추어 정렬되어 있기는 하지만, 다른 수를 입력해도 종료시간에 맞게 정렬되어 출력된다. 

 

정답 제출 출력값 

수정된 코드와 비교했을 때 종료 시간이 first 위치에 있는거 말고는 동일하게 정렬되었음을 확인 할 수 있다. 

 

Time 변수도 올바르게 수정하였고, for문도 수정된 코드에 맞게 수정하여 예제를 입력해보았다. 

 

예제

 

출력값

 

출력에도 이상이 없어서 정답을 제출해보았더니....

????

 

아무리 봐도 모르겠다...

정답으로 제출한 코드랑 수정된 코드의 동작 과정이 차이가 없어보이는데

어디서 잘못된건지 모르겠다. 

 

겸사겸사 해결될때 까지 계속해보고 

해결되는 대로 블로그에 남겨놔야겠다.