[Java] 백준 28107. 회전초밥

📌 문제 링크 - https://www.acmicpc.net/problem/28107

 

 

---

 

 

 

 

문제

회전 초밥 가게에 N명의 손님이 있고, 요리사는 M개의 초밥을 순서대로 만든다. 요리사가 초밥을 만들 경우, 1번 손님부터 N번 손님의 순서대로 그 초밥을 받게 된다. 만약 먼저 초밥을 받는 손님이 초밥을 먹을 경우, 뒤의 손님들은 해당 초밥을 먹을 수 없다. 만약 아무도 해당 초밥을 먹지 않는다면, 초밥은 버려진다.

 N명의 손님은 각자 먹고 싶은 초밥이 적힌 주문 목록을 가지고 있다. 목록에 적힌 초밥의 순서에 상관 없이 만약 목록에 적혀있는 초밥이 앞에 오면 반드시 먹는다. 만약, 목록에 적히지 않은 초밥을 받는다면 그 초밥은 반드시 먹지 않는다. 단, 손님들은 다양한 초밥을 먹고 싶어하기 때문에 각 종류의 초밥은 최대 한 번만 먹는다.

각 손님의 주문 목록과 순서대로 만들어지는 M개의 초밥이 주어질 때, 각 손님이 먹게 되는 초밥의 개수를 구해 보자.

 

 

입력

첫 번째 줄에 손님의 수 N과 초밥의 수 M이 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000;1 ≤ M ≤ 200,000)

두 번째 줄부터 N개의 줄에 걸쳐 각 손님에 대한 주문 목록을 나타내는 정수 k와 A1,A2,…,Ak가 공백으로 구분되어 순서대로 주어진다. k는 주문 목록에 적힌 초밥 종류의 개수이며, Ai는 주문 목록에 적힌 초밥 종류이다. (1 ≤ Ai ≤ 200,000)

각 손님의 주문 목록에 적힌 초밥 종류는 모두 다르며, 모든 손님에 대해 k의 합이 200,000 이하임이 보장된다.

 N+2번째 줄에 요리되는 초밥의 종류를 나타내는 M개의 정수 B1,B2,…,BM이 공백으로 구분되어 순서대로 주어진다. (1 ≤ Bi ≤ 200000)

 

 

출력

한 줄에 N개의 정수 C1,C2,…CN을 공백으로 구분하여 출력한다. Ci는 i번 손님이 먹은 초밥의 개수를 의미한다.

 

 

 

먼저 2번 손님이 3번 초밥과 2번 초밥을 먹는다. 이후, 1번 초밥이 제공되는데 1번 손님이 먼저 이를 먹기 때문에 3번 손님은 본인의 선호 목록에 1번 초밥이 있어도 이를 먹지 못한다. 이후 4번 초밥이 들어오는데 선호 목록에 4번 초밥이 있는 손님이 없으므로 바로 버려진다. 마지막으로 2번 손님이 5번 초밥을 먹게 된다.

따라서 1번 손님은 1개, 2번 손님은 3개, 3번 손님은 0개의 초밥을 먹게 된다.

 

 

---

 

 

풀이

손님이 먹고 싶은 주문 목록이 주어지면 우선순위 큐에 int[] {초밥 번호, 손님 번호} 형태로 저장해 준다. 이때 초밥 번호 기준 오름차순, 초밥 번호가 같다면 손님 번호 오름차순으로 정렬해 준다.

마찬가지로 요리되는 초밥의 종류인 B를 초밥 번호 오름차순으로 정렬해 준 후, 요리되는 초밥 종류를  for문을 통해 순회하면서 현재 초밥보다 더 작은 번호의 초밥이 주문 목록에 남아 있다면, 해당 초밥은 먹을 수 없으므로 주문 목록에서 제거해 주고, 주문 목록에 현재 초밥을 원하는 손님이 있다면 해당 손님이 먹은 초밥 개수를 증가시켜준다.

 

 

---

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// https://www.acmicpc.net/problem/28107
public class Main_28107 {
    private static final int SUSHI = 0, NUM = 1; // 초밥 번호, 손님 번호
    private static int N, M; // 손님의 수, 초밥의 수
    private static int[] B; // 요리되는 초밥의 종류
    private static int[] count; // i번 손님이 먹은 초밥의 개수
    private static PriorityQueue<int[]> orderList; // 각 손님에 대한 주문 목록


    public static void main(String[] args) throws IOException {
        init();
        sol();
        print();
    }//main


    private static void sol() {

        for(int sushi : B) {
            // 손님 주문 목록이 남아있고, 손님이 원하는 초밥이 없을 때
            while(!orderList.isEmpty() && orderList.peek()[SUSHI] < sushi) {
                orderList.poll();
            }

            // 손님 주문 목록이 남아있고, 손님이 원하는 초밥이 있을 때
            if(!orderList.isEmpty() && orderList.peek()[SUSHI] == sushi) {
                int n = orderList.poll()[NUM]; // 손님 번호
                count[n]++; // n번 손님이 먹은 초밥 개수 증가
            }
        }

    }//sol


    private static void print() {
        StringBuilder ans = new StringBuilder();

        // 손님이 먹은 초밥의 개수를 공백으로 구분하여 출력한다.
        for(int c : count) {
            ans.append(c).append(' ');
        }

        System.out.print(ans);
    }//print


    private static void init() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 손님의 수, 초밥의 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        B = new int[M];           // 요리되는 초밥의 종류
        count = new int[N];       // i번 손님이 먹은 초밥의 개수
        // 손님 주문 목록 : 초밥 번호 오름차순, 초밥 번호가 같다면 손님 번호 오름차순 정렬
        orderList = new PriorityQueue<>((o1, o2) -> {
            if(o1[SUSHI] == o2[SUSHI]) return o1[NUM] - o2[NUM];
            return o1[SUSHI] - o2[SUSHI];
        });

        // 각 손님에 대한 주문 목록
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken()); // 주문 목록에 적힌 초밥 종류의 개수
            for(int j=0; j<k; j++) {
                int sushi = Integer.parseInt(st.nextToken());
                orderList.offer(new int[] {sushi, i});
            }
        }

        // 요리되는 초밥의 종류
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<M; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }

        // 요리되는 초밥 번호 오름차순 정렬
        Arrays.sort(B);
        br.close();
    }//init


}//class