[Baekjoon] 28107_회전초밥

Silver I

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

---

< 회전초밥 >

 

문제 풀이 

 

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

1) 손님의 주문 목록 저장하는 우선순위 큐 [초밥 종류, 손님 번호]

2) 요리되는 초밥 종류 저장하는 우선순위 큐

 

 my solution (Java)

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

public class _28107_ { // 회전초밥

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

		int n = Integer.parseInt(st.nextToken());
		int m = 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]) {
					return o1[1] - o2[1];
				}
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(bf.readLine());
			int k = Integer.parseInt(st.nextToken());
			for (int j = 0; j < k; j++) {
				queue.add(new int[] { Integer.parseInt(st.nextToken()), i });
			}
		}

		PriorityQueue<Integer> num = new PriorityQueue<>();
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < m; i++) {
			num.add(Integer.parseInt(st.nextToken()));
		}

		int result[] = new int[n];
		while (!num.isEmpty()) {
			if(queue.isEmpty()) {
				break;
			}
			if (queue.peek()[0] == num.peek()) {
				int temp[] = queue.poll();
				num.poll();
				result[temp[1]] += 1;
			} else if (queue.peek()[0] > num.peek()) {
				num.poll();
			} else {
				queue.poll();
			}
		}

		for (int i = 0; i < n; i++) {
			bw.write(result[i] + " ");
		}
		bw.flush();
	}
}

 

Main

변수)
n : 손님의 수
m : 초밥의 수
queue : PriorityQueue <int []>에 [초밥 종류, 손님 번호] 저장
num: PriorityQueue <Integer>에 요리되는 초밥 종류 저장
result: i번 손님이 먹은 초밥의 개수 저장

 

- 손님의 수 (n)와 초밥의 수 (m) 입력

- 우선순위 큐에 [초밥 종류, 손님 번호] 입력받아 저장 (queue)

- 우선순위 큐에 요리되는 초밥 종류 저장 (num)

- num이 빌 때까지 반복

: queue가 비어있다면 손님이 초밥을 먹지 않으므로 종료

: queue와 num의 초밥 종류가 일치한다면 그 손님이 초밥을 먹음

: queue의 맨 앞 초밥 번호가 num의 맨 앞 초밥 번호보다 크다면 num의 맨 앞 초밥을 먹을 일이 없으므로 num.poll()

: num의 맨 앞 초밥 번호가 queue의 맨 앞 초밥 번호보다 크다면 queue의 맨 앞 초밥이 요리될 일이 없으므로 queue.poll()

- result 배열 출력

 

---

---