[백준] 12764. 싸지방에 간 준하

문제 링크

[백준] 12764. 싸지방에 간 준하

풀이 과정

다음 문제의 조건을 생각해봐야 합니다.

1. 싸지방에서 자리를 차지하고 있는 사람들.
2. 싸지방을 끝내고 나온 사람으로 인한 공석 자리들.

싸지방에서 자리를 차지하고 있는 사람들은 종료 시간이 가까운 순서대로 싸지방을 빠져 나옵니다. 즉, 종료 시간이라는 하나의 기준치로써 정렬이 되야하며, 동시에 가까운 순서대로 빠져나오기 위해 occupied 이라는 이름의 우선순위 큐를 사용합니다.

싸지방을 사용중인 사람 및 좌석 번호는 occupied 우선순위 큐에 저장되어 있습니다. 하다가 끝내고 나온 사람들로 인해 공석이 생기게 됩니다. 그 공석 번호를 따로 저장할 자료구조가 필요합니다. 공석인 자리들을 알고 있어야 다음 사람을 그 자리에 앉힐 수 있기 때문입니다.

가장 먼저 배열에 표시할 수 있습니다. 빠져나온 사람이 앉아있던 자리 번호를 인덱스로 배열에 체크하는 방법입니다. 하지만, 사람을 앉힐 때 공석 확인을 위한 불필요한 배열 순회가 발생시킬 수 있기 때문에 사용하지 않습니다.

공석 중 가장 작은 좌석 번호에 앉힌다는 문제의 조건에 따라 최소힙을 생각할 수 있습니다. 그러면, 맨 앞 요소가 가장 작은 좌석 번호일테니 꺼내기만 하면 되므로, 공석 확인을 위해 따로 순회 과정이 필요 없게 됩니다.

아래 예시를 통해 과정을 설명하겠습니다.

현재 싸지방에 세 명의 사람이 앉아 있고, 이번에 들어올 사람은 65-110 동안 싸지방을 이용하려고 합니다. 가장 먼저 끝나는 사람의 종료 시간은 50이며 앉아있는 좌석 번호는 2, 그 다음 사람의 종료 시간은 60이며 좌석 번호는 1, 마지막 사람의 종료 시간은 70이며 좌석 번호는 3입니다.

이번 사람이 들어오려는 시작 시간은 65 입니다. 따라서, 65 이하의 종료 시간을 갖는 사람들을 싸지방에서 모조리 뺀 다음 번호만 골라내 공석 번호를 담는 vacant 에 추가해줍니다. 빠진 순서는 (50, 2) → (60, 1) 이지만, 최소힙인 vacant 에는 공석번호가 오름차순으로 정렬되어 있는 것을 확인할 수 있습니다.

공석이 존재하기 때문에, 공석 번호 중 가장 작은 값이 맨 앞에 위치하므로, 그 번호를 뽑아내 이번 사람을 앉힙니다. 이번 사람은 110까지 싸지방을 이용할테니, 70에 끝나는 사람 뒤에 위치하게 됩니다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<int[]> list = new ArrayList<>();

        while (N-- > 0) list.add(Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray());

        Collections.sort(list, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        PriorityQueue<int[]> occupied = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o1[0] - o2[0];
            }
        });

        PriorityQueue<Integer> vacant = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return Integer.compare(o1, o2);
            }
        });

        int[] chairs = new int[100001];
        int newIdx = 1;

        for (int[] time : list) {
            while (!occupied.isEmpty() && occupied.peek()[0] <= time[0]) {
                vacant.add(occupied.poll()[1]);
            }

            if (vacant.isEmpty()) {
                occupied.add(new int[]{time[1], newIdx});
                chairs[newIdx]++;
                newIdx++;
            } else {
                int vacantIdx = vacant.poll();
                occupied.add(new int[]{time[1], vacantIdx});
                chairs[vacantIdx]++;
            }
        }

        StringBuilder sb = new StringBuilder();
        int cnt = 0;

        for (int i = 1; i < chairs.length; i++) {
            if (chairs[i] == 0) break;

            cnt++;
            sb.append(chairs[i] + " ");
        }

        System.out.println(cnt);
        System.out.println(sb);
    }
}