[자바] 백준 12764: 싸지방에 간 준하, TreeSet + 우선순위큐 풀이

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

 

주의해야 할 부분

사용 가능한 컴퓨터가 여러 대가 있다면 가장 앞에 위치한 컴퓨터를 사용해야 한다. 예를 들어, [2, 4, 5] 번 컴퓨터가 사용 가능하다면 2번 컴퓨터를 사용해야 한다.

 

문제 풀이

군대를 갔다온 남자라면 싸지방이 무엇인지 알 것이다. 물론 모른다고 해서 못 푸는 문제는 아니다. 싸지방의 크기는 작기 때문에 사용 가능한 컴퓨터는 제한적이다. 일반적으로는 사용 가능한 컴퓨터가 여러 대 있다면 아무 곳이나 앉아서 사용하겠지만, 본 문제에서는 가장 앞에 위치한 컴퓨터를 사용해야 한다고 한다. 따라서 싸지방에 들어왔을 때, (1)사용 중이지 않은 컴퓨터를 확인하고, (2)그 중에서 가장 앞에 위치한 컴퓨터를 사용하면 된다.

 

• times : N개의 (컴퓨터 사용 시간, 종료 시간)을 저장하되, 사용 시간이 빠른 순으로 저장한다. (우선순위 큐)
• useCount : N개의 컴퓨터 중에서, 각 컴퓨터를 사용한 횟수를 저장한다.
• pcQue : 현재 사용 중인 컴퓨터의 (컴퓨터 번호, 종료 시간)을 저장한다. 단, 종료 시간이 빠른 순으로 저장한다. (우선순위 큐)
• available : 사용 가능한 컴퓨터 번호를 저장한다. 가장 앞에 위치한 컴퓨터부터 사용해야 하므로, 컴퓨터 번호가 작은 순으로 저장한다. 여기서는 TreeSet을 사용하였지만 우선순위 큐를 사용할 수도 있다. 둘 다, 삽입 및 삭제에서 O(log N)의 시간 복잡도를 갖는다. 
• set : N명의 사람이 사용한 컴퓨터 번호를 저장한다. set의 특징으로 중복 데이터를 저장하지 않으므로, 최종적으로 어떤 컴퓨터가 사용되었는지 확인할 수 있다.

 

위 자료구조를 사용하여 코드를 작성하면 된다. 

1. times에 저장된 데이터를 가져온다. 이 데이터에는 컴퓨터의 (시작 시간, 종료 시간)이 저장되어 있다.
2. pcQue를 탐색하면서 사용이 종료된 컴퓨터를 제거한다. 1번에서 구한 컴퓨터 시작 시간을 기준으로 사용이 종료된 컴퓨터를 제거하면 된다.
3. 2번에서 제거된 컴퓨터의 번호를 available에 저장한다. available에는 사용 가능한 컴퓨터 번호가 저장되어 있다.
4. 사용 가능한 컴퓨터를 찾되 가장 앞에 위치한 컴퓨터를 사용한다. available에는 컴퓨터 번호가 작은 순서대로 저장되어 있으므로, pollFirst()를 통해 가장 앞에 위치한 컴퓨터를 사용하면 된다.

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());
        PriorityQueue<Time> times = new PriorityQueue<>();

        // 컴퓨터 시작-종료 시간 저장
        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            int start = Integer.parseInt(inputs[0]);
            int end = Integer.parseInt(inputs[1]);
            times.offer(new Time(start, end));
        }

        int[] useCount = new int[N]; // 컴퓨터별로 사용 횟수

        // 사용 중인 컴퓨터의 (컴퓨터 번호, 종료 시간) 저장
        // 빨리 종료되는 컴퓨터를 앞에 배치한다.
        PriorityQueue<int[]> pcQue = new PriorityQueue<>((p1, p2) -> p1[1] - p2[1]);

        // 사용 가능한 컴퓨터 저장
        TreeSet<Integer> available = new TreeSet<>();
        for (int i = 0; i < N; i++) {
            available.add(i);
        }

        // 싸지방에 필요한 컴퓨터 최소 개수
        // 모든 인원이 사용한 컴퓨터 번호를 저장한다.
        Set<Integer> set = new HashSet<>();

        while (!times.isEmpty()) {
            Time current = times.poll(); // 컴퓨터를 사용할 (시작 시간, 종료 시간)

            // 종료 시간이 지난 컴퓨터를 모두 반환한다.
            while (!pcQue.isEmpty()) {
                if (pcQue.peek()[1] > current.start) {
                    break;
                }
                int[] poll = pcQue.poll();
                available.add(poll[0]); // 사용 가능 상태로 복귀
            }

            // 사용 가능한 컴퓨터 중 가장 앞의 컴퓨터를 선택
            int pickIdx = available.pollFirst(); // 사용 가능한 컵퓨터를 가져오되, 컴퓨터 번호가 가장 작은 것을 가져온다.
            useCount[pickIdx]++; // 현재 컴퓨터의 사용 횟수 + 1
            pcQue.offer(new int[]{pickIdx, current.end}); // 현재 컴퓨터의 (번호, 종료 시간) 저장
            set.add(pickIdx);
        }

        StringBuilder sb = new StringBuilder();
        sb.append(set.size()).append("\n"); // 사용된 컴퓨터의 수
        for (int i = 0; i < useCount.length; i++) {
            if (useCount[i] == 0) {
                break;
            }
            sb.append(useCount[i]).append(" ");
        }

        System.out.println(sb);
    }

    static class Time implements Comparable<Time> {
        int start;
        int end;

        public Time(int s, int e) {
            start = s;
            end = e;
        }

        @Override
        public int compareTo(Time other) {
            return this.start - other.start;
        }
    }
}

 

Time 클래스를 사용하지 않고 2차원 배열로도 작성할 수 있다.

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());

        int[][] times = new int[N][2];
        for (int i = 0; i < N; i++) {
            String[] inputs = br.readLine().split(" ");
            int start = Integer.parseInt(inputs[0]);
            int end = Integer.parseInt(inputs[1]);
            times[i][0] = start;
            times[i][1] = end;
        }
        Arrays.sort(times, (t1, t2) -> {
            return t1[0] - t2[0];
        });

        PriorityQueue<Integer> available = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            available.add(i);
        }

        Set<Integer> visited = new HashSet<>();

        PriorityQueue<int[]> pcQue = new PriorityQueue<>((p1, p2) -> {
            return p1[1] - p2[1];
        });

        int[] useCounts = new int[N];
        for (int i = 0; i < N; i++) {
            int[] time = times[i];

            while (!pcQue.isEmpty()) {
                if (pcQue.peek()[1] > time[0]) {
                    break;
                }
                int[] poll = pcQue.poll();
                available.offer(poll[0]);
            }

            int pickIdx = available.poll();
            visited.add(pickIdx);
            useCounts[pickIdx]++;
            pcQue.offer(new int[]{pickIdx, time[1]});
        }

        StringBuilder sb = new StringBuilder();
        sb.append(visited.size()).append("\n");
        for (int i = 0; i < N; i++) {
            if (useCounts[i] == 0) {
                break;
            }
            sb.append(useCounts[i]).append(" ");
        }

        System.out.print(sb);
    }
}