BOJ 19640 - 화장실의 규칙

튜터로 활동하고 있는 교내 알고리즘 튜터링 ‘알튜비튜’의 우선순위 큐 챕터 과제 문제이다.
코드리뷰를 위해 문제를 풀어보았다.

문제

회사의 화장실을 사용하려고 한다. 줄을 선 순서대로 사용할 수 있다.
원래는 줄이 한 개지만, M개로 나뉘게 되었다.
줄을 M개로 나누면서, 사람들은 1번째부터 M번째 줄에 원래 줄 순서대로 한 명씩 들어간다. 예를 들어, M이 4라면 다음과 같다.

순서	들어가는 줄
1	1
2	2
3	3
4	1
5	2
…	…

줄이 여러 개가 되었으니, 화장실을 사용하는 규칙도 변경이 있다.
M개의 줄에서 맨 앞에 있는 사람 (여기서는 선두라고 부른다.)들을 서로 비교하여 규칙에 따라 사용할 수 있도록 한다.

근무 일수(D)가 가장 높은 사람
D가 가장 높은 사람이 여러 명이라면, 화장실이 급한 정도(H)가 높은 사람
D와 H가 같고, 모두 가장 높은 사람이 여러 명이라면, 줄의 번호가 가장 낮은 사람

데카는 N명의 줄에 서 있고, 앞에는 K명의 사람이 있다.
이 때, 데카가 화장실을 사용하기 위해선 몇 명이 화장실을 사용해야 할까?

문제 분해

이 문제에서 해야 하는 작업을 정리해보자.

기존 줄 1개를 M개의 줄로 분할.
M개의 줄의 선두 중 주어진 조건에 따라 한 명의 선두를 선택.
1. 근무 일수 D가 높은 사람
2. 화장실이 급한 정도 H가 높은 사람
3. 줄의 번호가 낮은 사람

아이디어 도출

과정을 그대로 시뮬레이션 하기 위해 queue를 사용하는 것이 가장 적절하다. (queue의 작동은 줄 서기와 유사하고, vector나 배열은 가장 앞 원소를 제거하는 기능이 없으므로)
데카의 위치를 기억하고, queue m개를 만들어 사원들을 집어넣은 후, 과정을 시뮬레이션하다 데카가 나오면 멈추고 해당 횟수를 리턴하면 된다.
이 때, 선두의 사원들 비교에 어떤 방법이 효율적일까?
- 1. 배열에 넣고 소트 (nlogn)
- 1. pq에 넣고 가장 앞 원소 꺼내기 (logn)
- 시간 복잡도가 2가 더 낮고, 또한 원소의 삽입이 잦으므로 매번 모든 원소를 정렬하는 것은 비효율적이다. 따라서 우선순위 큐를 통해 선두들의 순서를 관리해야겠다고 생각할 수 있다.

수도코드

queue<Person> v[m]

// 1. queue에 정보 입력
for (int i = 0; i < n; i++) {
    line_num = i % m;
    // Person 구조체는 (줄 번호, 줄에서의 순서, d, h로 이루어져 있다.)
    v[line_num] = {line_num, i / m, d, h}
}

// 2. pq 초기화
v에서 첫 원소만 빼서 pq에 push.

// 3. 시뮬레이션
cnt = 0 // 데카 앞 사람 수

while (true) {
    // i. pq의 front를 뽑고, deka와 같다면 종료. 아니라면 계속 
    next = pq.front(); pop();
    if pq == deka -> break;

    // ii. next랑 같은 줄에서 다음 사람을 뽑음. 그리고 pq에 삽입.
    line_num = next.line_num;
    if (!v[line_num].empty()) pq.push(v[line_num].front()); pop();
    deka++;
}

고민한 것들

이렇게만 봐서는 정말 간단한 시뮬레이션 + 자료구조 문제인데… 고민과 시행착오가 좀 있었다.

어떤 자료구조를 사용해야 할까?

줄을 세우는 문제라고 한다면, 당연히 queue를 자연스래 먼저 떠올리게 된다. 그래서 나도 자연스럽게 queue를 사용하려고 했지만, 걸리는 부분은 queue의 개수, 즉 줄의 개수인 M의 범위가 10e5까지였다는 점이었다.

이거 너무 큰 거 아닌가?하긴 했는데 메모리 제한이 1024MB로 넉넉해서 일단 그냥 질러봤다. 그리고 메모리 문제는 다행히 발생하지 않았다. (72416KB 사용)

참고로, 그냥 배열써도 문제는 없다. 큐를 사용한 건 모든 줄에서 앞 사람을 꺼내야 되기 때문에, 배열 쓰면 인덱스를 배열마다 저장해야 하는데 이게 실수하기 딱 좋다. 벡터도 pop_back을 쓸 생각이면 뒤집어서 배열을 채워야 하는데 이 때 배열 크기를 먼저 지정해줘야 하니까 계산을 해야 하고, 그게 아니라면 배열과 같다. 즉 실수하기 싫고 큐로 구현하는 게 편해서…ㅎㅎ

그리고 시간 초과

처음 제출한 코드의 시뮬레이션 로직을 보자.

int cnt = 0;
while (true) {
    priority_queue<Person, vector<Person>, Compare> pq;

    // 1. 선두 꺼내기
    for (auto &q : v) {
        if (q.empty()) continue;
        pq.push(q.front());
    }
    // 2. 뽑힌 선두 중 가장 높은 우선순위인 사람 꺼내기
    Person next = pq.top();
    pq.pop();

    // 3. 데카면 종료, 아니면 계속
        if (make_pair(next.line, next.order) == deka) break;

    for (auto &q : v) {
        if (!q.empty() && q.front().line == next.line && q.front()order == next.order) {
            q.pop();
            break;
        }
    }
    cnt++;
}

무엇이 문제일까?
바로 pq에 매 번 m개의 원소를 넣고 있다는 점이다.
1개의 원소를 pq에 삽입하면 시간 복잡도가 O(logn), 이걸 m번씩 하는데 또 전체 루프가 최대 n번만큼 돌 수 있으므로 대략 **O(n^2logn)**라는… 어마무시한 시간이 걸린다.

사실, pq에 매 번 새롭게 원소를 넣을 필요가 없다. 이전에 들어간 원소들은 남겨두고, 필요한 원소만 그때마다 넣어주는 방식이 더 효율적이다.

priority_queue<Person, vector<Person>, Compare> pq;

for (int i = 0; i < n; i++) {
    line = i % m;
    order = i / m;
    cin >> d >> h;

    Person p = {line, order, d, h};
    pq.push(p);
    }

하지만 답답했던 나는 그냥 모든 원소를 처음부터 pq에 때려 넣는다는 로직을 고안하였고, 결과적으로는 틀렸다ㅎㅎ

틀린 이유는, 선두인 사람들만 주어진 규칙에 따라 비교해야 하는데, 이러면 고려할 필요가 없는 아직 선두가 아닌 사람들까지 비교하게 되기 때문이다. 따라서 순서가 꼬인다. 먼저 튀어나오면 안 되는 사람이 먼저 튀어나올 수 있다.

while (true) {
    // 1. pq 초기화
    for (auto &q: v) {
        if (!q.empty()) {
            pq.push(q.front());
            q.pop();
        }
    }
    // 2. 뽑힌 선두 중 가장 높은 우선순위인 사람 꺼내기
    Person next = pq.top();
    pq.pop();

    // 3. 데카면 종료, 아니면 계속
    if (make_pair(next.line, next.order) == deka) break;
    cnt++;
}

앞서 pq에 매번 원소를 새롭게 넣는 문제를 개선하기 위해 다음과 같이 수정했다.
매 반복마다 v의 모든 q에서 원소를 하나씩 꺼내 pq에 넣어주는 방식이다.
이 또한 아직 선두가 아닌 원소를 먼저 pq에 넣어버려 순서가 꼬여버린다는 문제가 있다. 반드시 선두인 원소끼리만 비교해주어야 한다.

정답

따라서 다음과 같이 pq에서 원소가 빠져나가면, 해당 원소가 위치했던 줄에서 새로운 원소를 꺼내 pq에 삽입하면서, 각 줄의 선두만 pq에 포함될 수 있도록 수정하였다.

// 1. pq 초기화
for (auto &q: v) {
    if (!q.empty()) {
        pq.push(q.front());
        q.pop();
    }
}

while (true) {
    // 2. 뽑힌 선두 중 가장 높은 우선순위인 사람 꺼내기
    Person next = pq.top();
    pq.pop();

    // 3. 데카면 종료, 아니면 계속
    if (make_pair(next.line, next.order) == deka) break;

    // (4). 방금 사람 빼온 줄에서 새로운 사람 추가
    if (!v[next.line].empty()) {
        pq.push(v[next.line].front());
        v[next.line].pop();
    }
    cnt++;
}
cout < cnt;

후기

메모리는 생각보다 쉽게 초과되지 않는다.
그렇다고 해서 시간 초과 기준이 널널한 것은 또 아니다.
시뮬레이션 문제는 직접 시뮬레이션을 열심히 돌려보자. 그래야 작동 원리를 더욱 잘 이해할 수 있다.

문제#

문제 분해#

아이디어 도출#

수도코드#

고민한 것들#

어떤 자료구조를 사용해야 할까?#

그리고 시간 초과#

정답#

후기#

문제