[BOJ 백준] 1379번 : 강의실 2 (C++)

[BOJ 백준] 1379번 : 강의실 2 (C++)

목차

• 01. 개요
• 02. 접근 방식
• 03. 정답 코드
• 04. 마무리

---

01. 개요

출처

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

 

문제

 

입력

 

출력

 

예시

 

 

---

02. 접근 방식

 

요약

1. 모든 강의를 강의 시작 시간 기준으로 오름차순 정렬

2. 우선순위 큐에 강의실에 해당 강의가 종료되는 시간 기준으로 오름차순 정렬

3. 강의실 우선순위 큐에는 첫 번째 요소에 위치한 강의실이 항상 모든 강의실 중에서 강의가 가장 빨리 끝남.

4. 다음 강의 시작 시간과 비교해서, 강의실을 추가할지, 기존 강의실을 사용할지 결정

5. 4번 과정을 끝까지 반복해서 결과 출력

 

과정

강의실을 최소한으로 사용해야 하므로, 기존 강의실을 최대한 재활용해야 합니다.

그래서, 강의실에 강의가 종료되었으면, 다음 강의를 해당 강의실에서 진행할 수 있습니다.

 

여기서 문제를 읽어보면, 이전 강의의 종료 시간과 다음 강의의 시작 시간이 겹치는 것은 문제가 되지 않습니다.

 

먼저, 강의 시간이 가장 빠른 것부터 강의를 진행합니다.

그래서, 강의는 강의 시작 시간을 기준으로 오름차순 정렬이 필요합니다.

 

그 후, 강의를 추가할 때, 사용할 수 있는 강의실을 찾아봐야 합니다.

기존 강의실 중에서 가장 빠르게 강의가 끝나는 강의실과 다음 강의의 시작 시간을 비교해야 합니다.

해당 강의실에서 진행한 강의의 종료 시간이 다음 강의 시작 시간보다 빨리 끝나면(작거나 같으면), 해당 강의실에서 다음 강의를 진행합니다.

만약에, 그러한 강의실이 존재하지 않는다면, 강의실을 새롭게 하나 추가해야 합니다.

 

예시를 통해서 하나씩 확인하겠습니다.

 

1. 강의 시작 시간 기준으로 오름차순 정렬

여기서 종료 시간에 대해서는 별도의 조건문이 없으므로, 강의 종료 시간에 대한 오름차순은 필요하지 않습니다.

 

오름차순 작업이 완료되면, 강의를 하나씩 검사를 진행합니다. 

 

첫 강의는 강의실 목록에 어떤 강의실도 존재하지 않으므로, 반드시 새로운 강의실을 추가해야 합니다.

 

강의 번호는 3은 1번 강의실에 배정되었습니다.

새로운 강의실 번호를 관리하는 변수와 강의별로 배정된 강의실 번호에 대한 데이터 처리도 추가로 필요합니다.

 

다음 강의 번호인 1의 시작 시간(3)과 강의실 중에서 가장 빨리 끝나는 강의실의 강의 종료 시간(14)을 비교합니다.

시작 시간이 더 빠르므로, 강의실을 새롭게 추가해야 합니다.

2번 강의실은 늦게 생성되었지만, 1번 강의실보다 강의 종료 시간이 빠릅니다.

그래서, 우선순위 큐에 넣어 순서를 변경합니다.

 

강의실 목록 중에서 강의가 가장 빨리 끝나는 강의실만 검사하면, 다른 강의실은 검사할 필요가 없습니다.

그래서, 강의실 목록을 우선순위 큐로 관리합니다.

 

강의 번호 8번을 검사했을 때도, 강의실을 새롭게 추가합니다.

 

 

강의 번호 5번을 검사했을 때도, 강의실을 새롭게 추가합니다.

 

강의 번호 2번을 검사했을 때도, 강의실을 새롭게 추가합니다.

 

강의 번호 4번은 시작 시간이 12입니다.

강의실 목록 중 가장 앞에 있는 2번 강의실의 종료 시간(8)과 비교하면, 기존 강의가 이미 종료되었음을 알 수 있습니다.

그래서, 2번 강의실을 재사용합니다.

 

이와 같은 방법으로 6번 강의를 검사합니다.

 

마지막으로 7번 강의에 대해 검사를 진행합니다.

 

그 결과, 강의실 최소 사용 개수는 5개입니다.

각 강의별로 사용하는 강의실 번호는 아래와 같습니다.

1번 강의 : 2번 강의실

2번 강의 : 5번 강의실

3번 강의 : 1번 강의실

4번 강의 : 2번 강의실

5번 강의 : 4번 강의실

6번 강의 : 5번 강의실

7번 강의 : 1번 강의실

8번 강의 : 3번 강의실

 

이 문제는 가능한 경우에 대해 모두 정답 처리가 되므로, 예시의 출력에서 강의에 대한 배정된 강의실 결과가 달라질 수 있습니다.

하지만, 최소 강의실 사용 수는 같아야 합니다.

---

03. 정답 코드

// 골드 3 - 1379번 : 강의실 2
// 작성자 : free4760(jeonghoe22)

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

using namespace std;

// N개의 강의
// 최대한 적은 수의 강의실 -> 모든 강의
// 입력 : 강의 번호, 시작 시간, 종료 시간

// 1. 한 강의실에서는 1개 강의만 진행
// 2. 종료시간과 다른 강의의 시작 시간 겹치는 것은 상관 x

// 출력
// 필요한 강의실 최소 개수 K개
// 둘째 줄부터 N줄 걸쳐서 배정된 강의실 번호 출력

// 1. 강의를 시작 시간 기준 오름차순 정렬하고 강의 우선순위 큐에 넣기
// 2. 강의실 우선순위 큐에 사용 가능한 강의실이 있는 경우, 해당 강의실 사용
// 3. 강의실 우선순위 큐에 사용 가능한 강의실이 없는 경우, 강의실 추가

struct Lecture
{
    int number = 0;
    int start = 0;
    int end = 0;
    int room = 0;

    // 우선순위 큐 - 시작 시간 기준 오름차순으로 정렬
    bool operator<(const Lecture& other) const
    {
        return start > other.start;
    }
};

struct Room
{
    int number = 0;
    int end = 0;

    // 우선순위 큐 - 강의실에 대한 종류 시간 기준 오름차순으로 정렬
    bool operator<(const Room& other) const
    {
        return end > other.end;
    }
};

vector<Lecture> g_lectures;
priority_queue<Lecture> g_pq;

// 강의 정보 입력 및 우선순위 큐에 추가
void initLecture(const int N)
{
    g_lectures = vector<Lecture>(N);

    for(Lecture& lecture : g_lectures)
    {
        cin >> lecture.number >> lecture.start >> lecture.end;
        g_pq.push(lecture);
    }

    // 벡터에 있는 강의 정보는 강의 번호 순으로 정렬
    sort(g_lectures.begin(), g_lectures.end(), [](const Lecture& a, const Lecture& b)
    {
        return a.number < b.number;
    });
}

// 강의실 시뮬레이션
int simulate()
{
    priority_queue<Room> pq_room;
    int room_cnt = 0;

    // 강의에 대해서 모두 검사
    while(g_pq.empty() == false)
    {   
        Lecture lecture = g_pq.top();
        g_pq.pop();

        bool b_add_room = false;
        // 사용할 수 있는 강의실이 있는지 확인
        Room room;
        // 1. 비어 있으면 추가
        if(pq_room.empty()) b_add_room = true;
        // 2. 사용 가능한 강의실이 없음.
        else
        {
            room = pq_room.top();
            // 강의실에 있는 강의 종료 시간보다 강의 시작 시간이 더 적으면, 강의실 추가
            if(room.end > lecture.start) b_add_room = true;
        }

        // 강의실 추가
        if(b_add_room)
        {
            room_cnt++;
            pq_room.push({room_cnt, lecture.end});
            g_lectures[lecture.number-1].room = room_cnt;
        }
        // 기존 강의실에서 강의 진행
        else
        {
            pq_room.pop();
            room.end = lecture.end;
            pq_room.push(room);

            g_lectures[lecture.number-1].room = room.number;
        }
    }

    return room_cnt;
}

// 결과 출력
void printResult(const int K)
{
    cout << K << "\n";
    for(const Lecture& lecture : g_lectures)
    {
        cout << lecture.room << "\n";
    }
}

int main()
{
    // 입출력 최적화
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 강의 수 N
    int N;
    cin >> N;

    // 강의 정보 입력 및 우선순위 큐에 추가
    initLecture(N);

    // 강의실 시뮬레이션
    int K = simulate();

    // 결과 출력
    printResult(K);
}

 

---

04. 마무리

강의실을 시작 시간 기준으로 오름차순 할 때도 우선순위 큐를 사용했습니다.

지금 글을 작성하면서 다시 생각하니, vector 컨테이너와 sort 함수를 사용해, 오름차순을 진행해도 문제가 없었을 것 같습니다.

 

---

 

읽어주셔서 감사합니다.

틀린 내용 지적은 언제나 환영입니다!