백준 19640번 화장실의 규칙 (C++)

문제 링크 : https://www.acmicpc.net/problem/19640

19640번: 화장실의 규칙

문제 요약

 

1. n명의 사원들이 도착한 순서대로 m개의 줄로 나열된다. 이때 주인공인 데카의 앞에는 k명의 사람들이 있다.

(ex : n=6, m=3, k=2일 경우, 데카는 3번째 줄의 첫 번째 순서로 서게된다.)

2. n명의 사원수 만큼 근속일수, 화장실의 급한 정도의 값을 입력 받는다.

3. 다음의 우선순위대로 화장실을 이용하게 된다.

4. 데카의 앞에는 몇명의 사람들이 화장실을 이용하게 되는지 출력하라.

 

 

핵심 포인트

 

우선순위라는 키워드가 언급되었으니 priority_queue를 활용하면 쉽게 풀 수 있습니다.

단, 매번 각 줄에 맨 앞에 서있는 사람들의 우선순위만 비교해야하기 때문에, 모든 값들을 시작하자마자 priority_queue에 넣지 않고 중간 과정을 거쳐 일부의 값들만 우선순위큐에 넣어 값을 비교해야합니다.

 

 

문제 풀이

 

먼저 전체코드입니다. 부분적으로 나누어 설명을 진행하겠습니다.

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

struct wc {
    int d;
    int h;
    int g;
    int c;
};

struct comp { // 2
    bool operator()(wc& a, wc& b) {
        if (a.d != b.d) return a.d < b.d;
        else if (a.h != b.h) return a.h < b.h;
        else return a.g > b.g;
    }
};

int n, m, k, a, b, ans;
vector<wc> people;
vector<queue<wc>> lines;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> k; // n : 사원수, m : 줄의 수, k : 데카의 앞에 있던 사람 수 
    priority_queue<wc, vector<wc>, comp> pq;
    for (int i = 0; i < m; i++) { // 1
        queue<wc> q;
        lines.push_back(q);
    }
    for (int i = 0; i < n; i++) { // 1
        cin >> a >> b;
        lines[i % m].push({ a,b,i % m,i });
    }
    for (int i = 0; i < m; i++) { // 2
        if (lines[i].empty()) continue;
        pq.push(lines[i].front());
        lines[i].pop();
    }
    while (true) { // 3
        if (pq.top().c == k) break;
        int pos = pq.top().g;
        pq.pop();
        ans++;
        if (lines[pos].empty()) continue;
        pq.push(lines[pos].front());
        lines[pos].pop();
    }
    cout << ans << "\n"; // 4
    return 0;
}

 

1. 먼저 값을 입력받는 구간입니다.

vector<wc> people;
vector<queue<wc>> lines;

... (중간생략)

    for (int i = 0; i < m; i++) { // 1
        queue<wc> q;
        lines.push_back(q);
    }
    for (int i = 0; i < n; i++) { // 2
        cin >> a >> b;
        lines[i % m].push({ a,b,i % m,i });
    }

(1) 먼저 m개의 줄만큼 큐를 생성합니다.

m의 값이 몇인지 모르는 상황에서 단순하게 큐를 여러개 생성하는 것은 의미가 없으므로, vector의 값 타입을 queue<wc>로 선언하여 m개의 줄만큼 큐를 생성합니다.

(2) m개의 줄만큼 순서대로 도착하는 사람들의 정보를 입력받아 각 줄(큐)에 저장합니다.

 

2. 다음은 m개의 줄의 맨 앞에 서있는 사람들을 우선순위 큐에 저장하는 과정입니다.

유의사항은 모든 사람을 우선순위 큐에 저장하는 것이 아닌, 맨 앞에 있는 사람들만 저장하는 것입니다.

struct comp {
    bool operator()(wc& a, wc& b) { // 3
        if (a.d != b.d) return a.d < b.d;
        else if (a.h != b.h) return a.h < b.h;
        else return a.g > b.g;
    }
};

... (중간생략)

    priority_queue<wc, vector<wc>, comp> pq;
    for (int i = 0; i < m; i++) {
        if (lines[i].empty()) continue; // 1
        pq.push(lines[i].front()); // 2
        lines[i].pop(); // 4
    }

(1) 만약 i번째 줄이 비어있다면 continue합니다.

(2) 그렇지 않을 경우 i번째 줄의 맨 앞에 있는 사람을 pq에 저장합니다.

(3) 주의사항은 우선순위 큐의 정렬 방식입니다. 문제에서는 아래와 우선순위로 사람들을 정렬해야합니다.

-> 근속년수가 긴 사람 > 화장실이 급한정도가 큰 사람 > 줄의 번호가 낮은 사람

-> 하지만 3번의 정렬순서를 보면 바로 윗줄에 나와있는 우선순위가 뒤바껴있는것을 확인할 수 있습니다.

-> 이유는 우선순위 큐는 일반적인 정렬과는 반대로 정렬해야하기 때문입니다. 이유인 즉슨, c++의 priority queue에서 우선순위의 값이 클 수록 말 그대로 우선순위의 번호가 큰것을 의미합니다. 우선순위의 번호가 1에 가까울수록 (작을수록) 더 앞의 순서로 오게됩니다.

(4) 그렇게 i번째 줄의 맨 앞의 사람을 저장하게되면 lines[i]번째의 큐를 pop해줍니다.

 

3. 다음은 정답을 구하는 마지막 구간입니다.

    while (true) {
        if (pq.top().c == k) break; // 1
        int pos = pq.top().g; // 2
        pq.pop(); // 3
        ans++;
        if (lines[pos].empty()) continue; // 4
        pq.push(lines[pos].front()); // 5
        lines[pos].pop();
    }
    cout << ans << "\n"; // 6

(1) pq.top()의 c의 값(몇 번째로 줄을 서게 됐는지 순서)이 k라면 데카라는 뜻이므로, while문을 종료합니다.

(2) 그렇지 않을 경우 현재 pq.top()이 몇번째 줄에 서있는지를 pos에 저장합니다.

(3) pq.top()을 pop해주고 ans의 값을 +1합니다.

(4) 만약 lines[pos]가 비어있다면 continue를 해줍니다.

(5) lines[pos]의 맨 앞에 있는 사람을 다시 pq에 저장합니다.

이렇게 해서 새로 줄을 서게된 사람은 pq내부에서 정렬이 됩니다.

그런다음 lines[pos]의 front를 pop해줍니다.

(6) 정답을 출력합니다.