백준 12764 싸지방에 간 준하 자바(java)

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

12764번: 싸지방에 간 준하

 

풀이 방법

우선순위 큐(Priority Queue) 3개를 사용하여 구현하였다.

시작 시각이 빠른 사람부터 컴퓨터에 배치하는 데 사용 가능한 컴퓨터, 즉 시작할 시각보다 더 빨리 종료되는 컴퓨터 중 작은 번호의 컴퓨터에 배치시켜야 한다. 따라서 시작 시각, 종료 시각, 번호에 대한 순서가 필요하다.

 

필요한 우선순위 큐 3개

1. 대기 중인 사용자 큐 users -> 시작 시각이 빠른 기준

2. 사용 중인 컴퓨터 큐 usingComs -> 사용 종료 시각이 빠른 기준

3. 비어 있는 컴퓨터 큐 emptyComs -> 컴퓨터의 번호가 작은 기준

 

풀이 흐름은 아래와 같다.

1. 각 컴퓨터의 사용 횟수를 저장하기 위해 컴퓨터 번호를 인덱스로 하는 useCnt 배열을 선언한다.

2. 대기 중인 사용자 큐 users 에서 사용자를 하나 꺼낸다.

3. usingComs 큐에서 사용자의 시작 시각보다 종료 시각이 작은 컴퓨터들의 번호를 emptyComs 에 넣는다.

4. emptyComs 큐가 비어 있다면 사용 가능한 컴퓨터가 없다는 것이므로 컴퓨터를 증설하여 배치한다.

5. emptyComs 큐가 비어 있지 않다면 poll 하여 꺼낸 컴퓨터 번호에 사람을 배치한다.

사람을 배치할 땐 해당 컴퓨터의 useCnt 카운트를 늘리고 usingComs 에 컴퓨터 번호와 종료 시각을 넣는다.

 

 

코드

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

public class Main {

    static class User {
        int start;
        int end;

        public User(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<User> users = new PriorityQueue<>(Comparator.comparing(user -> user.start)); // 사용자 시작 시각 빠른 순
        PriorityQueue<int[]> usingComs = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1]; // 종료 시각 빠른 순
            }
        });
        PriorityQueue<Integer> emptyComs = new PriorityQueue<>(); // 컴퓨터 번호 작은 순

        for(int i=0; i<N; i++) {
            String[] line = br.readLine().split(" ");
            int start = Integer.parseInt(line[0]);
            int end = Integer.parseInt(line[1]);
            users.add(new User(start, end));
        }

        int X = 0; // 컴퓨터 개수
        int[] useCnt = new int[N+1];
        while(!users.isEmpty()) {
            User user = users.poll();
            // 지금 사용할 수 있는 컴퓨터 찾기
            while(!usingComs.isEmpty()) {
                int[] com = usingComs.peek();
                int num = com[0];
                int endTime = com[1];
                if(endTime <= user.start) {
                    emptyComs.add(num);
                    usingComs.poll();
                } else {
                    break;
                }
            }

            // 비어있는 컴퓨터가 없다면 컴퓨터 증설
            if(emptyComs.isEmpty()) {
                usingComs.add(new int[]{++X, user.end});
                useCnt[X]++;

            } else {
                int num = emptyComs.poll();
                useCnt[num]++;
                usingComs.add(new int[]{num, user.end});
            }
        }

        System.out.println(X);
        for(int i=1; i<=X; i++) {
            System.out.print(useCnt[i] + " ");
        }
    }
}