[백준 11000번] - 강의실 배정(C/C++)

[문제 설명]

---

[문제 풀이]

풀다보니.. 답을 맞추긴 했지만.. 코드가 좀.. 그렇다..

다른 사람들을 봤을때 우선순위 큐를 사용해서 문제를 푼거같은데.. 나중에 한번 다시 풀어봐야겠다.

내가 문제를 푼 방식은 아래와 같다.

 

1. sort함수를 사용해서 시작 시간이 빠른 순서로, 시작 시간이 같다면 강의 시간이 짧은 순서로 정렬했다.

2. isvisited 배열을 선언하여 방문 여부를 체크한다.

3. 방문하지 않은 인덱스일 경우 count를 증가시킨다.

4. 현재 강의가 끝나는 시간보다 큰 시작 시간을 갖는 인덱스를 lower_bound를 통해 구한다.

5. 찾은 인덱스가 방문하지 않은 곳이라면 방문 상태로 변경하고, 방문한 곳이라면 인덱스를 하나 증가시켜서 다시 확인한다.

6. lower_bound로 더이상 구할 수 없을때까지 4,5번을 반복한다.

7. 모든 강의를 탐색할때까지 3번으로 돌아간다.

 

파이팅 !

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

#include <bits/stdc++.h>
using namespace std;
bool isvisited[200001];
bool compare(const pair<int,int>&a, const pair<int,int>&b)
{
    if(a.first < b.first)
    {
        return true;
    }
    else if(a.first > b.first)
    {
        return false;
    }
    else
    {
        return (a.second - a.first) < (b.second - b.first);
    }

}

bool compare2(const pair<int,int>&a, const pair<int,int>&b)
{
    return a.first < b.first;
}

int main()
{
    vector<pair<int,int>> v;
    int n;
    cin >> n;
    for(int i =0; i < n ;i++)
    {
        int s,t;
        cin >> s >> t;
        v.emplace_back(make_pair(s,t));
    }

    sort(v.begin(), v.end(), compare);

    int count = 0;

    for(int i =0; i < n; i++)
    {
        if(isvisited[i] == true) continue;
        isvisited[i] = true;
        count++;
        auto iter = lower_bound(v.begin(), v.end(), pair<int,int>(v[i].second,0) , compare2);
        while(1)
        {
            if(iter == v.end())
            {
                break;
            }
            int idx = iter - v.begin();
            if(isvisited[idx] == true)
            {
                ++iter;
            } 
            else
            {
                isvisited[idx] = true;
                iter = lower_bound(v.begin(), v.end(), pair<int,int>((*iter).second,0) , compare2);        
            }
        }
    }
    cout << count << "\n";
}