[Boj_12764] 싸지방에 간 준하

📎 문제 링크

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

 

▸ 문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.

마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.

하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.

컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.

준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

 

▸ 입력

첫째 줄에 사람의 수를 나타내는 N이 주어진다. (1 ≤ N ≤ 100,000)둘째 줄부터 N개의 줄에 걸쳐서 각 사람의 컴퓨터 이용 시작 시각 P와 종료 시각 Q가 주어진다. (0 ≤ P < Q ≤ 1,000,000)

시작 시각이나 종료 시각이 다른 사람과 겹치는 경우는 없다.

 

▸ 출력

첫째 줄에 사람이 모든 사람이 기다리지 않아도 되는 컴퓨터의 최소 개수 X를 출력한다.

둘째 줄에는 1번 자리부터 X번 자리까지 순서대로 각 자리를 사용한 사람의 수를 띄어쓰기 간격으로 출력한다.

 

📍 문제 정보

• 🥇 문제 레벨 : 골드 3
• 🔔  문제 유형 : 구현, 자료구조, 시뮬레이션, 우선순위 큐
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

우선순위 큐를  두 개를 사용해서 풀 수 있는 문제이다.

 

먼저, 입력받은 사람들의 컴퓨터 이용 시간을 시작 시각이 작은 것을 기준으로 정렬해 준다.

 

컴퓨터 사용을 완료하면 해당 자리는 비게 된다.

다음 사람은 현재 빈자리 중에서 번호가 가장 작은 자리에 앉아야 한다.

즉, 빠른 종료 시각을 가진 사람들의 컴퓨터 번호 중 가장 작은 컴퓨터 번호를 가진 컴퓨터를 이용한다.

 

따라서 우선순위 큐 두 개를 선언한 뒤,

우선순위 큐 1에는 컴퓨터의 번호와 종료 시각을 저장하며, 종료 시각이 작은 것을 기준으로 정렬한다.

우선순위 큐 2에는 사용 가능한 컴퓨터 번호를 저장한다.

 

컴퓨터를 이용 중인 사람의 종료 시각보다 현재 사람의 시작 시각이 더 커서 컴퓨터 사용이 가능하다면,

사용 가능한 컴퓨터의 번호를 우선순위 큐 2에 저장한다.

 

우선순위 큐 2가 비어있지 않다면, 사용 가능한 컴퓨터가 있으므로 해당 컴퓨터의 사용자 수를 1 증가시키고

우선순위 큐 1에 컴퓨터 번호와 해당 컴퓨터를 사용할 사용자의 종료 시각을 저장한다.

 

우선순위 큐 2가 비어있다면, 사용 가능한 컴퓨터가 없으므로 새로운 컴퓨터를 생성하고

우선순위 큐 1에 새로운 컴퓨터 번호와 해당 컴퓨터를 사용할 사용자의 종료 시각을 저장한다.

 

위 풀이대로 코드를 작성해 보면 아래와 같다.

 

✔ 최종 코드

메모리 : 53484KB
시간 : 648ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static public class Time implements Comparable<Time> {
        int start; int end;
        public Time(int start, int end) {
            this.start = start; this.end = end;
        }
        @Override
        public int compareTo(Time o) {
            return this.start - o.start;
        }
    }
    static public class Pos implements Comparable<Pos> {
        int idx; int end;
        public Pos (int idx, int end) {
            this.idx = idx; this.end = end;
        }
        @Override
        public int compareTo(Pos o) {
            return this.end - o.end;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        ArrayList<Time> list = new ArrayList<>();
        StringTokenizer st;
        int start, end; // 시작 시간, 종료 시간
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            start = Integer.parseInt(st.nextToken());
            end = Integer.parseInt(st.nextToken());

            // 시작 시간이 빠른 순
            list.add(new Time(start, end));
        }
        Collections.sort(list);

        int cnt = 0; // 컴퓨터의 최소 개수
        int[] room = new int[100001]; // 각 자리를 사용한 사람의 수

        PriorityQueue<Pos> pq = new PriorityQueue<>(); // 종료 시간이 빠른 순
        PriorityQueue<Integer> idx = new PriorityQueue<>(); // 사용 가능한 컴퓨터의 번호

        for (Time now : list) {
            // 컴퓨터를 사용할 수 있다면
            while (!pq.isEmpty() && pq.peek().end < now.start) {
                // 사용 가능한 컴퓨터 번호 저장
                idx.offer(pq.poll().idx);
            }

            if (!idx.isEmpty()) {
                Integer i = idx.poll();
                room[i] += 1;
                pq.offer(new Pos(i, now.end));
            } else { // 사용 가능한 컴퓨터 X
                cnt++; // 새로운 컴퓨터 생성
                room[cnt] += 1;
                pq.offer(new Pos(cnt, now.end));
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append(cnt).append("\n");
        for (int i = 1; i <= cnt; i++) {
            sb.append(room[i]).append(" ");
        }
        System.out.println(sb.toString());
    }
}

 

해결 완료 ! 🔥