[JAVA] 백준 12764 : 싸지방에 간 준하

문제

12764번: 싸지방에 간 준하

 

해결방법

대기하는 인원 없이 모두가 싸지방에 오자마자 컴퓨터를 이용하는데 필요한 컴퓨터의 개수를 구하고

각 자리별로 사용한 인원을 구하는 문제이다.

 

총 3개의 우선순위 큐를 활용했다.

1. waitQ -> 대기인원 : 시작 시간이 적은 사람부터 먼저 꺼내서 확인하기 위함
2. playerQ -> 이용인원 : 현재 싸지방을 이용 중인 사람
3. comQ -> 사용가능한 컴퓨터 : 사용 가능한 컴퓨터의 번호 (1 ~ 100000)

또 2개의 정렬 class를 활용

1. Person : 시작시간과 종료시간을 가지고 있으며 시작 시간 기준으로 정렬 -> waitQ에 활용
2. Player : 종료시간과 이용하고 있는 컴퓨터 번호를 가지고 있으며 종료 시간 기준으로 정렬 -> playerQ에 활용

---

코드에서 // 탐색 시작

이후 부분 코드의 설명

 

정렬된 대기인원을 사용해 시작 시간이 적은 인원부터 컴퓨터를 사용하게 해 준다.
이때 이미 이용 중인 인원이 있다면 현재 인원의 시작 시간보다 이용 중인 인원의 종료 시간이 더 빠른지 확인한다.

• 빠르다면 해당 인원은 종료시키고 그 인원이 사용하던 컴퓨터의 번호를 comQ에 넣어준다.
• 아니라면 더 이상 탐색하지 않음(종료 시간으로 정렬되어서 추가로 탐색해도 현재 인원의 시작 시간보다 종료 시간이 더 늦음)

이후 사용 가능한 컴퓨터를 확인한다(comQ)

• 만약 사용가능한 컴퓨터가 있다면(누군가 사용하다 종료한 경우) 해당 컴퓨터를 현재 인원이 사용하게끔 해주고 used에 사용한 사람이 추가되었음을 표시
• 없다면 index(코드에서 max) 번호의 컴퓨터를 할당해준다. (가용할 컴퓨터 대수가 늘어나게 됨)

대기인원이 없을 때까지 반복.

 

반복문 종료 후 used 배열이 0인 부분까지 탐색한다(0이면 그 이전 인덱스 수만큼의 컴퓨터 대수가 필요하다는 뜻)
문제의 출력에 맞게 출력

 

코드

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

public class Main {

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

		int n = Integer.parseInt(br.readLine());

		// 대기 인원 -> 시작 시간이 작은 순서대로 꺼내기위해 정렬
		PriorityQueue<Person> waitQ = new PriorityQueue<>();
		for (int i = 0; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int sTime = Integer.parseInt(st.nextToken());
			int eTime = Integer.parseInt(st.nextToken());

			waitQ.offer(new Person(sTime, eTime));
		}

		// 싸지방을 이용 중인 인원 -> 본인 시간보다 종료 시간이 작은 사람 꺼내기 -> 종료 시간 작은 순서대로 정렬
		PriorityQueue<Player> playerQ = new PriorityQueue<>();

		// 사용가능한 컴퓨터 확인용
		PriorityQueue<Integer> comQ = new PriorityQueue<>();

		// 컴퓨터 사용 횟수
		int[] used = new int[100001];

		// 탐색 시작
		int max = 1;
		while (!waitQ.isEmpty()) {
			Person person = waitQ.poll();

			// 본인보다 종료시간이 이전인 사람 추출
			while (!playerQ.isEmpty()) {
				if (person.sTime >= playerQ.peek().eTime) {
					comQ.offer(playerQ.poll().cIdx);
				} else break;
			}

			// 가능한 곳에 본인 입장
			if (comQ.isEmpty()) {
				playerQ.offer(new Player(person.eTime, max));
				used[max]++; // 사용 횟수 표시
				max++;
			} else {
				int cIdx = comQ.poll();
				used[cIdx]++; // 사용 횟수 표시
				playerQ.add(new Player(person.eTime, cIdx));
			}
		}


		for (int i = 1; i < 100001; i++) {
			if (used[i] == 0) {
				max = i - 1;
				break;
			}
			sb.append(used[i] + " ");
		}

		System.out.println(max);
		System.out.println(sb);
	}

	static class Person implements Comparable<Person> {
		int sTime;
		int eTime;

		Person(int sTime, int eTime) {
			this.sTime = sTime;
			this.eTime = eTime;
		}

		@Override
		public int compareTo(Person o) {
			return sTime - o.sTime;
		}
	}

	static class Player implements Comparable<Player> {
		int eTime;
		int cIdx; // 사용 중인 컴퓨터 번호

		Player (int eTime, int cIdx) {
			this.eTime = eTime;
			this.cIdx = cIdx;
		}

		@Override
		public int compareTo(Player o) {
			return eTime - o.eTime;
		}
	}
}