백준 12764 (싸지방에 간 준하) - 정렬, 우선순위큐

문제

---

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

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

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

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

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

 

 

 

 

풀이

---

우선순위 큐를 이용해서 시간을 정렬하면서 푸는 문제다.

 

처음 우선순위큐를 사용해서 풀었더니 오답이 나왔다. 현재 컴퓨터를 사용하고자하는 사람의 시작시간이 가장 빠른 종료시간의 사람보다 느리면 넣어주는 방식을 사용하였다.

 

하지만 이렇게 했을경우 반례가 발생한다.

 

그래서 고친 알고리즘 순서는 이렇다.

 

• 사람들의 시간리스트를 시작시간을 기준으로 정렬을 한다.
• 현재사람의 시작시간보다 종료시간이 빠른 모든 컴퓨터를 빼준다.
• 사람이 없는 컴퓨터가 있다면 배정하고 아니면 새로 컴퓨터를 추가한다.

위와 같은 방식으로 구현을 하면된다. 

 

사용하지 않는 컴퓨터가 여러개일 경우 번호가 작은것부터 쓰는게 규칙이므로 우선순위큐를 두개 사용해서 풀었다.

 

현재 시작하려는 사람의 시작시간보다 빠르게 종료된 컴퓨터를 모두 꺼내주고 리스트에 컴퓨터 번호를 넣어준다.

while(!computerList.isEmpty()) {
				
	computer top = computerList.peek();
	if(list.get(i).startTime > top.endTime) {
		pq.add(top.num);
		computerList.poll();
	}
	else 
		break;
}

<전체코드>

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

public class Main {	

	static StringBuilder sb = new StringBuilder();
	
	static class computer implements Comparable<computer>{
		
		public int startTime;
		public int endTime;
		public int num;
		
		public computer(int num, int endTime, int startTime) {
			this.num = num;
			this.endTime = endTime;
			this.startTime = startTime;
		}
		
		public void setEndTime(int endTime) {
			this.endTime = endTime;
		}
		
		@Override
		public int compareTo(computer c) {
			return this.endTime - c.endTime;
		}
	}
	
	static class time implements Comparable<time>{
		
		public int startTime, endTime;
		
		public time(int startTime, int endTime) {
			this.startTime = startTime;
			this.endTime = endTime;
		}
		
		@Override
		public int compareTo(time t) {
			return this.startTime - t.startTime;
		}
	}
	
	static int[] answer = new int[100000];
	public static void main(String[] args) throws IOException{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(bufferedReader.readLine());
		List<time> list = new ArrayList<time>();
		
		for(int i = 0 ; i <n ; i++) {
			StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
			list.add(new time(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
		}
		
		Collections.sort(list);
		
		PriorityQueue <computer> computerList = new PriorityQueue<computer>();
		PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
		int idx = 0;
		
		for(int i = 0 ; i < n ; i++) {
			while(!computerList.isEmpty()) {
				
				computer top = computerList.peek();
				if(list.get(i).startTime > top.endTime) {
					pq.add(top.num);
					computerList.poll();
				}
				else 
					break;
			}
			
			if(!pq.isEmpty()) {
				int index = pq.poll();
				answer[index]++;
				computerList.add(new computer(index, list.get(i).endTime, list.get(i).startTime));
			}
			else {
				computerList.add(new computer(idx, list.get(i).endTime, list.get(i).startTime));
				answer[idx] = 1;
				idx++;
			}
		}
		
		
		sb.append(idx + "\n");
		
		for(int i = 0 ; i < idx ; i++) {
			sb.append(answer[i] + " ");
		}
		
		System.out.println(sb);
	}
}