문제
N명이 M개의 줄에 서서 화장실을 이용한다. 사람들은 도착 순서대로 M개의 줄에 번갈아 배치된다(i번째 사람은 i % M 번 줄에 선다). 화장실 칸이 비면 다음 규칙으로 줄에서 한 명씩 입장한다:
- 우선순위: 화장실 입장 횟수(d)가 많은 사람, d가 같으면 이용 시간(h)이 적은 사람, h도 같으면 줄 번호(l)가 작은 사람이 먼저 입장한다.
K번째 사람(0-indexed)이 화장실에 들어가기 전에 몇 명이 입장하는지 출력하라.
입력
첫째 줄에 N, M, K가 주어진다. 이후 N개의 줄에 i번째 사람의 이용 횟수 d와 이용 시간 h가 주어진다.
- 1 ≤ K ≤ N ≤ 100,000
- 1 ≤ M ≤ N
출력
K번째 사람이 입장하기 전까지 화장실에 입장한 사람 수를 출력한다.
예제
입력:
5 2 3
1 2
3 1
2 5
1 3
2 1출력:
2풀이
핵심 아이디어: 각 줄을 큐(Queue)로 관리하고, 줄의 맨 앞 사람들을 **우선순위 큐(PriorityQueue)**에 올려두어 매번 가장 높은 우선순위의 사람을 선택한다.
- 초기화: M개의 큐에 사람들을 순서대로 배분한다. i번째 사람(0-indexed)은
i % M번 큐에 들어간다. - 우선순위 큐 초기화: 각 줄의 첫 번째 사람(헤드)을 우선순위 큐에 삽입한다.
- 시뮬레이션: 우선순위 큐에서 최우선 사람을 꺼낸다.
- 꺼낸 사람이 K번째 사람이면 종료한다.
- 아니라면, 해당 사람이 있던 줄의 다음 사람을 우선순위 큐에 추가하고, 카운터를 증가시킨다.
- 우선순위 비교: d(이용 횟수)가 클수록, h(이용 시간)가 작을수록, 줄 번호(l)가 작을수록 높은 우선순위를 갖는다.
코드
package day349;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Day332BOJ19640화장실의규칙 {
static int N, M, K;
static Queue<int[]>[] q;
static PriorityQueue<int[]> pq;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
q = new LinkedList[M];
for (int i = 0; i < M; i++) {
q[i] = new LinkedList<>();
}
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int d = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
int l = i % M;
q[l].add(new int[] { d, h, l, i });
}
pq = new PriorityQueue<>((o1, o2) -> {
if (o1[0] < o2[0])
return 1;
else if (o1[0] == o2[0]) {
if (o1[1] < o2[1])
return 1;
else if (o1[1] == o2[1]) {
return o1[2] - o2[2];
} else
return o2[1] - o1[1];
}
return o2[0] - o1[0];
}); // 와우
for (int i = 0; i < M; i++) {
if (!q[i].isEmpty())
pq.add(q[i].poll());
}
System.out.println(solve());
br.close();
}
private static int solve() {
int cnt = 0;
while (!pq.isEmpty()) {
int[] cur = pq.poll();
if (cur[3] == K)
break;
if (!q[cur[2]].isEmpty())
pq.add(q[cur[2]].poll());
cnt++;
}
return cnt;
}
}복잡도
- 시간: O(N log M) — 각 사람이 우선순위 큐에 삽입/삭제될 때 O(log M)
- 공간: O(N) — 큐들과 우선순위 큐 합산