(백준) 싸지방에간 준하 _ 12764

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

 

🐢 설명

싸지방 컴퓨터를 사용하는 순서가 주어졌을 때 최소 몇개의 컴퓨터가 있어야 대기없이 컴퓨터를 사용할 수 있는지 구하는 문제이다.

이때 사용가능한 컴퓨터 중에서 번호가 가장 빠른 컴퓨터 사용한다는 점이 중요하다.

 

1. 모든 컴퓨터의 이용시간을 시작 시간을 기준으로 user_우선순위큐에 넣는다.

2. 사용하는 컴퓨터를 담는 usingCom_우선순위큐에는 끝나는 시간을 기준으로 담는다.

2-1. 만약 usingCom이 없다면 컴퓨터 자리를 새로 만들어서 추가한다.

2-2. 만약 usingCom이 있다면 자신의 시작 시간과 컴퓨터의 사용가능한 시간대를 확인하고 가능한 컴퓨터의 자리는 좌석순서_우선순위큐에 담는다.

2-2-1. 좌석순서_우선순위큐가 비어있다면 시간대가 맞는 컴퓨터가 없고 전부 사용중이라는 뜻이므로 새로 추가한다.

2-2-2. 그렇지 않다면 하나를 뽑아서 좌석번호를 인덱스로 사용횟수를 늘려주고, usingCom 큐에 시작시간-끝시간 쌍을 넣어준다.

 

🐢코드

package Gold이상문제_정리;

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

public class 싸지방에간준하_12764 {
    static int[] arr = new int[100001];
    static int N;
    static PriorityQueue<Computer> usingCom = new PriorityQueue<>(Comparator.comparing(c -> c.end));
    static PriorityQueue<Computer> user = new PriorityQueue<>(Comparator.comparing(c -> c.start));
    static PriorityQueue<Integer> remainSeat = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        int seat = 0;

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            user.add(new Computer(start, end));
        }

        while (!user.isEmpty()) {
            Computer userTime = user.poll();
            int start = userTime.start;
            int end = userTime.end;

            // no computer
            if (usingCom.isEmpty()) {
                usingCom.add(new Computer(++seat, start, end));
                arr[seat]++;
            }
            // find usable computer
            else {
                while (!usingCom.isEmpty()) {
                    Computer com = usingCom.peek();

                    // 사용가능
                    if (com.end < start) {
                        remainSeat.add(com.number);
                        usingCom.poll();
                    } else if (com.end > start) {
                        break;
                    }
                }

                // 사용가능한 컴퓨터 없음
                if (remainSeat.isEmpty()) {
                    usingCom.add(new Computer(++seat, start, end));
                    arr[seat]++;
                }
                // 사용가능한 컴퓨터 있음
                else {
                    int seatNum = remainSeat.poll();
                    arr[seatNum]++;
                    usingCom.add(new Computer(seatNum, start, end));
                }
            }
        }

        StringBuilder answer = new StringBuilder();
        answer.append(seat).append("\n");
        for (int i = 1; i <= seat; i++) {
            answer.append(arr[i]).append(" ");
        }
        System.out.println(answer);
    }

    private static class Computer {
        int number;
        int start;
        int end;

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

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

🐢 마무리