[Baekjoon] 19640_화장실의 규칙

Gold IV

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

---

< 화장실의 규칙 >

 

문제 풀이 

 

우선순위 큐를 사용해서 문제를 해결했다.

 

우선순위 큐에는 [근무 일수, 화장실이 급한 정도, 줄 번호, 원래 순서, 데카 여부]를 저장한다.

우선 순서는 근무 일수(내림차순) > 화장실이 급한 정도(내림차순) > 줄 번호(오름차순)이다.

 

 my solution (Java)

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

public class _19640_ { // 화장실의 규칙

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

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

		int idx = 0;
		int check = 0;

		ArrayList<int[]> arr = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int d = Integer.parseInt(st.nextToken());
			int h = Integer.parseInt(st.nextToken());

			if (i == k)
				check = 1;
			else
				check = 0;

			arr.add(new int[] { d, h, idx, i, check });
			idx += 1;
			if (idx == m)
				idx = 0;
		}

		int result = 0;

		for (int i = 0; i < m; i++) {
			if (i >= n)
				break;
			queue.add(arr.get(i));
		}

		while (true) {
			int temp[] = queue.poll();
			if (temp[4] == 1)
				break;
			result += 1;
			if (temp[3] + m < n) {
				queue.add(arr.get(temp[3] + m));
			}
		}

		System.out.println(result);
	}
}

 

Main

변수)
n : 사원의 수
m : 새로운 줄의 수
k : 자신의 앞에 서 있던 사원의 수
queue : [근무 일수, 급한 정도, 줄 번호, 원래 순서, 데카 여부] / 근무 일수(내림차순) > 화장실이 급한 정도(내림차순) > 줄 번호(오름차순)
idx : 줄 번호
check : 데카 여부
arr : [근무 일수, 급한 정도, 줄 번호, 원래 순서, 데카 여부]
d : 근무 일수
h : 급한 정도
result : 데카가 이용하기까지 몇 명이 사용했는지 출력

 

- 사원의 수(n), 새로운 줄의 수(m), 자신의 앞에 서 있던 사원의 수(k) 입력

- ArrayList에 [근무 일수, 급한 정도, 줄 번호, 원래 순서, 데카 여부] 저장

- 새로운 줄 수만큼 처음에 사람을 채움

: 지시한 새로운 줄의 수보다 사원의 수가 적을 수 있으므로 남은 사원이 없으면 종료

- 한 줄을 채웠다면 사원을 화장실에 보냄

: 보낸 후 그 줄의 다음 사람을 queue에 저장

: 화장실 간 사람이 데카라면 종료

---

---