[Baekjoon] 2594_놀이공원

Silver III

문제(출처: https://www.acmicpc.net/problem/2594)

---

< 놀이공원 >

 

문제 풀이 

 

입력받은 시간을 분으로 바꾼 후 우선순위 큐를 사용하여 휴식시간을 찾는다.

 

* 함께할 수 있는 시간이 없다면 0을 출력한다.

* 1030 1300/ 1200 1250 입력이 들어온다면 1030부터 1300까지 운영하는 것과 같다.

 

 my solution (Java)

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

public class _2594_ { // 놀이공원

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

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

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if (o1[0] == o2[0]) {
					return o1[1] - o2[1];
				}
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());

			String x = st.nextToken();
			String y = st.nextToken();

			int start = Integer.parseInt(x.substring(0, 2)) * 60 + Integer.parseInt(x.substring(2, 4));
			int end = Integer.parseInt(y.substring(0, 2)) * 60 + Integer.parseInt(y.substring(2, 4));

			queue.add(new int[] { start, end });
		}

		int result = queue.peek()[0] - 10 - 600;
		int temp[] = null;
		while (!queue.isEmpty()) {
			temp = queue.poll();
			temp[1] += 10;

			while (!queue.isEmpty()) {
				if (temp[1] >= queue.peek()[0] - 10) {
					temp[1] = Math.max(queue.poll()[1] + 10, temp[1]);
				} else {
					result = Math.max(result, queue.peek()[0] - 10 - temp[1]);
					break;
				}
			}
		}

		result = Math.max(result, 22 * 60 - temp[1]);

		if (result < 0)
			result = 0;

		System.out.println(result);
	}
}

변수)
n : 놀이기구 개수
queue : 우선순위 큐 [시작시간, 끝나는 시간]
x, y : 운행시작 시각, 종료 시각 String형
start, end : 운행시작 시각, 종료 시각을 분으로 바꾼 값
result : 함께할 수 있는 가장 긴 시간
temp : 운행시간

 

놀이기구 개수를 입력받는다. 우선순위 큐를 선언하는데 [운행시작 시간, 운행 종료 시간]을 저장하며 운행 시작 시간이 빠른 것을 우선순위로 둔다. 시작 시간이 같다면 종료 시간이 빠른 것을 우선순위로 둔다. 놀이기구 개수만큼 운행 시작 시간과 운행 종료 시간을 입력받아 분으로 바꾼 후 우선순위 큐에 저장한다. 

함께할 수 있는 가장 긴 시간 result를 (우선순위 큐의 맨 앞에 있는 값의 시작 시간-10) - 600으로 초기화한다. 우선순위 큐가 빌 때까지 다음 과정을 반복한다.

 

1) queue에서 값 poll 한 후 temp에 저장

2) 놀이기구 작동 멈춘 후 10분 후까지 쉴 수 없으므로 종료 시간+10

3) 우선순위 큐가 빌 때까지 다음 과정을 반복한다.

3-1) temp의 종료 시간 값이 (queue 값의 시작 시간 - 10) 보다 크거나 같다면 temp에서 구한 놀이기구가 작동하는 동안 다음 놀이기구도 같이 작동한다는 뜻이다. 그러므로 종료 시간을 현재 종료시간과 (queue 값의 종료시간+10) 중에서 큰 값으로 저장한다.

3-2) 3-1번의 조건과 일치하지 않는다면 temp의 놀이기구가 멈추고 휴식시간을 가진 후에 다음 놀이기구가 운행된다는 뜻이다. 그러므로 현재 result 값과 ((다음 놀이기구 시작 시간-10) - temp 종료시간) 중에서 큰 값으로 저장한다.

 

마지막으로 현재 result 값과 (오후 10시 - temp 종료시간) 중에서 큰 값으로 저장한다.

만약 result 값이 0보다 작다면 함께할 수 있는 시간이 없는 것이므로 0으로 저장한다.

 

최종 result를 출력한다. 

---

---