[백준BOJ] 12764번 싸지방에 간 준하.java

 

 

백준 저지에서 싸지방에 간 준하를 자바를 통해 풀어 보았다. 

 

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

12764번: 싸지방에 간 준하

 

12764번 싸지방에 간 준하.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

12764번 싸지방에 간 준하

문제

현재 대한민국 해군에 소속되어있는 준하는 문제를 풀기 위해 매일같이 사이버 지식 정보방 통칭 싸지방에 다닌다. 그러나 최근 문제가 생겼다. 싸지방에 사람이 몰려 컴퓨터 수가 모자라게 된 것이다. 이런 사태를 도저히 용납할 수 없었던 준하는 곧 전역하는 선임을 설득해 민원을 넣도록 하는 데 성공했다.
마침내 부대에서는 민원을 받아들이기로 하였고, 컴퓨터를 증설하기로 했다. 또한, 컴퓨터 간의 사용률에 따라 다른 성능의 컴퓨터를 설치하고자 한다.
하지만 예산이 부족해 사람 수 만큼 컴퓨터를 살 수가 없었다. 고심에 고심을 거듭한 준하는 모든 사람이 항상 정해진 시간에 싸지방을 이용한다는 사실을 발견했다.
컴퓨터가 있는 자리에는 1번부터 순서대로 번호가 매겨져 있다. 모든 사람은 싸지방에 들어왔을 때 비어있는 자리 중에서 번호가 가장 작은 자리에 앉는 것이 규칙이다.
준하가 발견한 사실과 이용 규칙을 가지고, 모든 사람이 기다리지 않고 싸지방을 이용할 수 있는 컴퓨터의 최소 개수와 자리별로 몇 명의 사람이 사용했는가를 구하시오.

설명

우선순위 큐를 통해 시간을 줄여 푸는 문제이다.

 

각 사람들은 시작 시간과 종료 시간이 정해져있다. 편의를 위해서 시작 시간을 기준으로 정렬했다.

 

컴퓨터 사용을 완료하면 해당 자리가 비게 된다. 다음 사람은 현재 빈 자리 중에 번호가 가장 빠른 자리에 앉아야 한다. 즉 현재 사람의 시작 시간보다 빠른 종료 시간을 가진 사람들의 컴퓨터 번호 중 가장 작은 컴퓨터 번호를 가진 컴퓨터를 사용한다. 

 

따라서 종료 시간과 컴퓨터 번호를 저장하며 종료 시간에 대해 정렬하는 우선순위 큐(A)와 컴퓨터 번호에 대한 우선순위 큐(B)를 설정한다.

 

현재 사람의 시작 시간과 A의 peek과 비교하여 현재 사람의 시작 시간이 더 크다면 A에서 poll하고 poll된 노드에서 컴퓨터 번호를 B에 삽입한다. 즉 현재 사람이 사용 가능한 컴퓨터 번호를 B에 저장하는 것이다.

 

B는 현재 사람이 사용가능한 컴퓨터가 번호순으로 정렬되어 있다. 따라서 B의 poll은 현재 사람이 사용할 컴퓨터 번호이다.

 

만약 B가 비어있다면 현재 사람이 사용 가능한 컴퓨터가 없다는 의미이므로 새로운 컴퓨터를 생성한다.

코드

//12764번 싸지방에 간 준하.java
package boj20220105;

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

public class 싸지방에_간_준하_12764 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static class time implements Comparable<time>{
    	int P;
    	int Q;
    	time(int P, int Q){
    		this.P=P;
    		this.Q=Q;
    	}
		@Override
		public int compareTo(time o) {
			return Integer.compare(this.P, o.P);
		}
    }
    static class computer implements Comparable<computer>{
    	int Q;
    	int index;
    	computer(int Q, int index){
    		this.Q=Q;
    		this.index=index;
    	}
		@Override
		public int compareTo(computer o) {
			return Integer.compare(this.Q, o.Q);
		}
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
		int N = Integer.parseInt(br.readLine());
		PriorityQueue<time> times = new PriorityQueue<>();
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int P = Integer.parseInt(st.nextToken());
			int Q = Integer.parseInt(st.nextToken());
			times.add(new time(P, Q));
		}
		
		PriorityQueue<computer> comEndTime = new PriorityQueue<>();
		PriorityQueue<Integer> nextCom = new PriorityQueue<>();
		int[] comIndex = new int[100001];
		int comCount=0;
		
		for(int i=0;i<N;i++) {
			while(!comEndTime.isEmpty() && times.peek().P > comEndTime.peek().Q) {
				nextCom.add(comEndTime.poll().index);
			}
			
			if(nextCom.isEmpty()) {
				comEndTime.add(new computer(times.poll().Q, comCount));
				comIndex[comCount]++;
				comCount++;
			}
			else {
				comEndTime.add(new computer(times.poll().Q, nextCom.peek()));
				comIndex[nextCom.poll()]++;
			}
		}
		
		sb.append(comCount+"\n");
		for(int i=0;i<comCount;i++) {
			sb.append(comIndex[i]+" ");
		}
		System.out.println(sb.toString());
	}
}