[BOJ 백준] 12764 - 싸지방에 간 준하, Java(자바)

문제

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

12764번: 싸지방에 간 준하

풀이

먼저 입력을 시작 시간이 빠른 순서대로 우선순위 큐 pq에 넣는다. 종료 시간이 빠른 순서대로 이용 중인 컴퓨터를 담는 우선순위 큐 computers, 사용 가능한 컴퓨터를 번호가 작은 순서대로 담는 우선순위 큐 available, 컴퓨터 번호 순서대로 이용자 수를 담을 배열 arr을 생성한다. pq에서 한 명씩 빼면서 사용 가능한 컴퓨터가 있는지 확인해 available에 담고, 가장 앞의 컴퓨터를 이용 중으로 담는다. 사용 가능한 컴퓨터가 없다면 새로운 num을 늘려 새로운 컴퓨터를 추가한다.

코드

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

class Node {
    int start, end, number;
    
    Node(int start, int end) {
        this.start = start;
        this.end = end;
    }
    
    Node(int start, int end, int number) {
        this.start = start;
        this.end = end;
        this.number = number;
    }
}

public class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(in.readLine());
        int num = 0;
        int[] arr = new int[100001];
        PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>() {
           @Override
           public int compare(Node o1, Node o2) {
               return o1.start - o2.start;
           }
        });
        PriorityQueue<Node> computers = new PriorityQueue<Node>(new Comparator<Node>() {
          @Override
          public int compare(Node o1, Node o2) {
              return o1.end - o2.end;
          }
        });
        PriorityQueue<Integer> available = new PriorityQueue<Integer>();
        
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(in.readLine());
            pq.offer(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        
        // arr[num]++;
        // computers.offer(new Node(pq.peek().start, pq.poll().end, num++));
        while (!pq.isEmpty()) {
            while (!computers.isEmpty() && computers.peek().end < pq.peek().start)
                available.offer(computers.poll().number);
            
            if (available.isEmpty()) {
                arr[num]++;
                computers.offer(new Node(pq.peek().start, pq.poll().end, num++));
                continue;
            }
            
            int tmp = available.poll();
            arr[tmp]++;
            computers.offer(new Node(pq.peek().start, pq.poll().end, tmp));
        }
        System.out.println(num);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < num; i++)
            sb.append(arr[i] +" ");
        System.out.println(sb);
    }
}