백준 19640 (화장실의 규칙) - java

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

 

문제

데카는 회사의 화장실을 이용하려고 했다. 하지만 수도 시설 고장으로 회사 내의 모든 화장실 사용이 금지됐고, 사원들은 단 하나의 임시 화장실을 이용해야 했다.

임시 화장실의 앞에 데카를 포함한 N명의 사원이 대기하고 있다. 데카는 N명의 줄에서 K + 1번째로 줄을 섰다. 즉, 데카보다 먼저 도착한 사람이 K명이 있다. 줄이 길어지자 사장은 M개의 줄로 나눠서 대기하라 하였다.

N명의 사원은 순서대로 M개의 줄로 나눠 섰다. 기존 줄의 1번째 사원은 1번째 줄에, 2번째 사원은 2번째 줄에, ... M번째 사원은 M번째 줄에, 그리고 M + 1번째 사원은 1번째 줄의 뒤에 서는 방식이다. 

M개의 줄로 나눠 선 것을 본 사장은 매우 흡족해하며 자리를 떠났다.

M개의 줄의 사원들은 암묵적으로 다음의 규칙에 따라 화장실을 이용하기로 하였다.

• 선두란, 어떤 줄에서 가장 먼저 와서, 가장 앞에 선 사람을 말한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 화장실을 이용한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상인 경우, 해당 선두들 중 화장실이 급한 정도 Hi가 가장 높은 선두가 화장실을 이용한다.
• M개의 줄의 선두 중 근무 일수 Di가 가장 높은 선두가 둘 이상이며, 해당 선두들의 화장실이 급한 정도 Hi도 모두 같다면, 해당 선두 중 줄의 번호가 가장 낮은 줄에 선 선두가 화장실을 이용한다.

과연 몇 명의 사원이 화장실을 이용하고 나서야 데카의 차례가 올까? 매우 초조해지기 시작한 데카를 대신해 계산해주자.

 

유형 : 우선순위 큐 + 큐

 

접근 방식

• 라인의 개수 m개만큼의 큐를 선언하고 순서대로 추가한다.
• 처음에 각 큐의 각 선두들만 우선순위 큐에 추가한다.
• 우선순위 큐에서 한 명씩 제거 하고 해당 줄에 해당하는 선수를 큐에서 빼서 추가한다.

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int n,m,k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        PriorityQueue<Turn> pq = new PriorityQueue<>(
                (x,y) -> {
                    if(x.d == y.d) {

                        if(x.h == y.h) {
                            return x.l - y.l;
                        }

                        return y.h - x.h;
                    }

                    return y.d - x.d;
                }
        );

        Queue<Turn>[] qList = new ArrayDeque[m+1];
        for(int i = 1 ; i <= m ; i++) {
            qList[i] = new ArrayDeque<>();
        }

        int curL = 1;

        for(int i = 1 ; i <= n ; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int d = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            qList[curL].add(new Turn(i,curL,d,h));

            curL++;

            if(curL > m) {
                curL = 1;
            }
        }

        for(int i = 1 ; i <= m ; i ++) {
            if(!qList[i].isEmpty()) {
                pq.add(qList[i].poll());
            }
        }

        int result = 1;

        while(!pq.isEmpty()) {
            Turn cur = pq.poll();

            if(cur.idx == k + 1) {
                break;
            }

            if(!qList[cur.l].isEmpty()) {
                pq.add(qList[cur.l].poll());
            }

            result++;
        }


        System.out.println(result - 1);
        br.close();
    }
}

class Turn {
    int idx;
    int l;
    int d;
    int h;

    Turn(int idx,int l,int d,int h) {
        this.idx = idx;
        this.l = l;
        this.d = d;
        this.h = h;
    }
}