백준 19640번 - 화장실의 규칙 [JAVA]

TaeBong·2023년 1월 7일

알고리즘 풀이

목록 보기

13/14

🧩 문제

▶ 백준 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도 모두 같다면, 해당 선두 중 줄의 번호가 가장 낮은 줄에 선 선두가 화장실을 이용한다.
과연 몇 명의 사원이 화장실을 이용하고 나서야 데카의 차례가 올까? 매우 초조해지기 시작한 데카를 대신해 계산해주자.

입력

첫 번째 줄에는 임시 화장실에 대기하고 있는 사원의 수 N (1 ≤ N ≤ 105), 사장이 지시한 새로운 줄의 수 M (2 ≤ M ≤ 105), 데카가 화장실에 도착했을 때 자신의 앞에 서 있던 사원의 수 K (0 ≤ K ≤ N − 1)가 빈칸을 사이에 두고 주어진다.

두 번째 줄부터 각 N개의 줄에 임시 화장실에 i번째로 줄을 섰던 사원의 근무 일수 Di (0 ≤ Di ≤ 36,500), 화장실이 급한 정도를 나타내는 정수 Hi (0 ≤ Hi ≤ 108)가 가장 먼저 도착한 사원부터 빈칸을 사이에 두고 주어진다.

출력

데카가 화장실을 이용하기까지 몇 명의 사원이 화장실을 이용할 것인지 출력한다.

예제

입력

출력

🎯 풀이

메모리	시간	코드길이
61568 KB	728 ms	3178 B

1. 사원 클래스 생성

private static class Employee {
    boolean isDeka; //이 객체가 데카인지 확인
    int days, hurry, lineNum;    //근무 일수, 급한 정도, M개의 줄 중에 몇번째 줄에 서있었는지(0~M-1)

    public Employee(boolean isDeka, int days, int hurry, int lineNum) {
        this.isDeka = isDeka;
        this.days = days;
        this.hurry = hurry;
        this.lineNum = lineNum;
    }
}

화장실을 이용하기 위해서 줄을 서 있는 사원들의 정보를 저장하는 클래스를 만든다. 우선순위를 결정하기 위한 정보들을 넣어준다.

2. 각 줄의 선두에 있는 사원들

//각 줄의 선두에 있는 사람의 집합
PriorityQueue<Employee> firsts = new PriorityQueue<Employee>(
        (o1, o2) -> o1.days == o2.days ?
                (o1.hurry == o2.hurry ?
                        (o1.lineNum - o2.lineNum)
                        : o2.hurry - o1.hurry)
                : o2.days - o1.days
);

//선두 사원들 초기 세팅
for(int i = 0; i < M; i++) {
    if(lines[i].size() > 0) {
        firsts.add(lines[i].poll());
    } else break;
}

각 줄의 선두를 모아둔 우선순위 큐를 만든다. 근무일수, 급한정도는 내림차순으로, 줄번호는 오름차순으로 우선순위임을 주의해야한다. 우선순위 큐를 생성한 후, 초기 세팅으로 M명의 사람들을 넣어준다. 단, 사장이 나눈 줄의 수(M)보다 줄을 서 있는 사원이 더 적을 경우를 대비하여 조건문을 넣어준다.

3. 화장실에 입장

while(true) {
    ++cnt;
    Employee curEmployee = firsts.poll();

    //데카가 화장실에 들어갔으면 while문 중단
    if(curEmployee.isDeka) break;

    if(lines[curEmployee.lineNum].size() > 0) {
        firsts.add(lines[curEmployee.lineNum].poll());
    }
}

System.out.println(cnt-1);

우선순위 큐에 있는 선두들 중 가장 우선순위가 높은 사원을 삭제한다. 그 사원이 데카라면 while문을 중단시키고, 아니라면 방금 삭제된 사원이 있던 줄의 사원을 우선순위 큐에 추가한다. 이때, 해당 줄에 사람이 없다면 뽑지 않는다. 데카가 화장실을 이용하기 전까지 몇명의 사원이 화장실을 이용했는지이므로 cnt-1값을 출력시킨다.

⭐️ 전체 풀이 코드

package G4;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BJ19640_화장실의규칙 {

    private static class Employee {
        boolean isDeka; //이 객체가 데카인지 확인
        int days, hurry, lineNum;    //근무 일수, 급한 정도, M개의 줄 중에 몇번째 줄에 서있었는지(0~M-1)

        public Employee(boolean isDeka, int days, int hurry, int lineNum) {
            this.isDeka = isDeka;
            this.days = days;
            this.hurry = hurry;
            this.lineNum = lineNum;
        }
    }

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

        int N = Integer.parseInt(st.nextToken());   //임시 화장실에 대기하고 있는 사원의 수
        int M = Integer.parseInt(st.nextToken());   //사장이 지시한 새로운 줄의 수
        int K = Integer.parseInt(st.nextToken());   //화장실에 도착했을 때 자신의 앞에 서있던 사원의 수


        Queue<Employee>[] lines = new LinkedList[M]; //사람들이 M개의 줄에 서 있음
        for(int i = 0; i < M; i++) {
            lines[i] = new LinkedList<Employee>();
        }

        //N명의 사원들을 M개의 줄로 나눠세움
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            boolean isDeka = false;
            int days = Integer.parseInt(st.nextToken());
            int hurry = Integer.parseInt(st.nextToken());
            int lineNum = i%M;

            if(i == K) {    //지금 나눠세우는 사람이 데카라면 true 처리
                isDeka = true;
            }

            lines[lineNum].add(new Employee(isDeka, days, hurry, lineNum));
        }

        //각 줄의 선두에 있는 사람의 집합
        PriorityQueue<Employee> firsts = new PriorityQueue<Employee>(
                (o1, o2) -> o1.days == o2.days ?
                        (o1.hurry == o2.hurry ?
                                (o1.lineNum - o2.lineNum)
                                : o2.hurry - o1.hurry)
                        : o2.days - o1.days
        );

        //선두 사원들 초기 세팅
        for(int i = 0; i < M; i++) {
            if(lines[i].size() > 0) {
                firsts.add(lines[i].poll());
            } else break;
        }

        int cnt = 0;
        while(true) {
            ++cnt;
            Employee curEmployee = firsts.poll();

            //데카가 화장실에 들어갔으면 while문 중단
            if(curEmployee.isDeka) break;

            if(lines[curEmployee.lineNum].size() > 0) {
                firsts.add(lines[curEmployee.lineNum].poll());
            }
        }

        System.out.println(cnt-1);

    }   //main 끝

}