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

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

19640번: 화장실의 규칙

 

풀이 방법

우선순위 큐를 사용하는 것이 핵심이다. 우선순위 큐는 일반적인 큐의 구조와 같이 FIFO(First In First Out) 를 지키지만 먼저 들어온 데이터 순서가 아닌 우선순위에 따라 우선순위가 높은 데이터 순서대로 나간다.

풀이 흐름은 아래와 같다.

 

1. 사람을 입력받으면서 차례대로 M개의 줄에 사람을 한 명씩 배치한다.

2. 우선순위 큐에 각 줄의 선두를 꺼내어 삽입한다.

    이때, 근무 일수가 높은 순, 근무 일수가 같다면 화장실 급한 정도가 높은 순, 급한 정도가 같다면 

    줄 번호가 낮은 순으로 우선순위를 주도록 Comparator 를 통한 정렬 기준 설정이 필요하다.

3. 우선순위 큐에서 한 명씩 추출하여 카운트하고 해당 사람이 있던 줄의 새로운 선두를 꺼내어 큐에 삽입한다.

4. 현재 추출된 사람의 번호가 K+1 이라면 데카의 차례이므로 루프를 탈출하고 앞 사람의 수를 출력한다.

 

코드

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

public class Main {

    static class Person {
        int day;
        int hurry;
        int lineNum;
        int num;

        public Person(int day, int hurry, int lineNum, int num)  {
            this.day = day;
            this.hurry = hurry;
            this.lineNum = lineNum;
            this.num = num;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int N = Integer.parseInt(line[0]);
        int M = Integer.parseInt(line[1]);
        int K = Integer.parseInt(line[2]);

        // M 개의 줄로 사람 나누기
        Map<Integer, List<Person>> linePeople = new HashMap<>();
        for(int i=0; i<N; i++) {
            String[] p = br.readLine().split(" ");
            int d = Integer.parseInt(p[0]); // 근무 일수
            int h = Integer.parseInt(p[1]); // 화장실 급한 정도
            int lineNum = (i % M) + 1; // 줄 번호
            int n = i+1; // 몇번째 사람인지, 첫번째 사람 1번부터 시작

            if(!linePeople.containsKey(lineNum)) {
                linePeople.put(lineNum, new ArrayList<>());
            }
            linePeople.get(lineNum).add(new Person(d, h, lineNum, n)); // 해당 줄에 사람 배치
        }

        // 우선순위 큐
        PriorityQueue<Person> waitingPeople = new PriorityQueue<>(new Comparator<Person>() {
            @Override
            public int compare(Person o1, Person o2) {
                if(o1.day == o2.day) { // 근무 일수가 같은 경우
                    if(o1.hurry == o2.hurry) { // 급한 정도가 같은 경우
                        return o1.lineNum - o2.lineNum; // 줄 번호가 작은 순
                    }
                    return o2.hurry - o1.hurry; // 급한 정도가 높은 순
                }
                return o2.day - o1.day; // 근무 일수가 높은 순
            }
        });

        // 각 줄 별 선두를 우선순위 큐에 삽입
        for(int i=1; i<=linePeople.keySet().size(); i++) {
            if(!linePeople.get(i).isEmpty()) {
                waitingPeople.add(linePeople.get(i).remove(0));
            }
        }

        int cnt = 0; // 사용한 사람 수 카운트
        while(!waitingPeople.isEmpty()) {
            Person person = waitingPeople.poll();
            cnt++;

            // 데카의 차례라면 종료
            if(person.num == K+1) {
                break;
            }
            // 현재 사람이 빠지고 새로운 선두를 큐에 삽입
            if(!linePeople.get(person.lineNum).isEmpty()) {
                waitingPeople.add(linePeople.get(person.lineNum).remove(0));
            }
        }
        System.out.println(cnt-1); // 데카의 차례까지 세었으므로 앞 사원들의 수는 -1
    }
}