Written by JS970
on March 10, 2023

1931 - 회의실 배정

난이도: 실버 1
날짜: 2023년 3월 10일
상태: Correct
추가 검토 여부: No
알고리즘 : 그리디 알고리즘

Solution

모든 선택에 있어서 선택 가능한 선택지 중 끝나는 시간이 가장 빠른 회의를 선택한다면 가장 많은 회의를 진행할 수 있게 된다.
이를 알고리즘으로 쉽게 구현하기 위해 pair를 사용했다.
- 끝나는 시간이 빠른 것을 선택해야 하므로 끝나는 시간을 pair.first로 설정한다.
- 이렇게 하면 sort를 이용해 원하는 상태로 한번에 정렬이 가능하다.
- 이전에 끝난 시간보다는 회의가 끝나는 시간이 같거나 뒤여야 하기 때문에 이를 조건문으로 구현하였다. 조건을 만족한다면 회의가 열렸다는 것을 의미하므로 이 때마다 count를 1씩 증가시킨다.
초기 코드에서는 끝나는 시간을 pair.second로 설정해서 정렬을 여러 번 해야 했다.
- 결과적으로 시간복잡도가 늘어나서 시간초과가 발생하였다.

code

초기 코드

while 문 내부에서 minSecond함수를 수행하는데 이 과정에서 시간복잡도가 O(n^2)으로 늘어나 시간초과 발생의 원인이 되었다.

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

int pointRenew(int cmpnum, pair<int, int> arr[], int arrSz, int currentPoint)
{
    for(int i = currentPoint; i < arrSz; i++)
    {
        if(arr[i].first >= cmpnum && arr[i].first == arr[i].second) return i+1;
        else if(arr[i].first >= cmpnum) return i;
    }
    return -1;
}

int minSecond(pair<int, int> arr[], int arrSz, int currentPoint)
{
    int min = INT_MAX;
    for(int i = currentPoint; i < arrSz; i++)
        min = (arr[i].second < min) ? arr[i].second : min;
    return min;
}

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

    int N;
    cin >> N;
    pair<int ,int> * arr = new pair<int, int>[N];
    for(int i = 0; i < N; i++)
        cin >> arr[i].first >> arr[i].second;
    sort(arr, arr+N);

    int point = 0;
    int min;
    int count = 0;
    while(point != -1 && point < N)
    {
        min = minSecond(arr, N, point);
        point = pointRenew(min, arr, N, point);
        count++;
    }
    cout << count << endl;

    return 0;
}

제출 코드

코드 구현에 있어 우선적으로 고려되어야 하는 회의 종료 시간을 pair.first로 설정하였기 때문에 정렬을 두 번씩 할 필요가 없다.

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

int main() {
    int n;
    cin >> n;
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i].second >> arr[i].first;
    }
    sort(arr, arr + n);

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

    return 0;
}

ref

1931번: 회의식 배정

Top