[백준] 28107 회전초밥 - Java

 

 

 

문제 출저

 

 

 

 

문제 풀이

손님들이 원하는 초밥이 있고 초밥들이 순서대로 제공합니다. 손님 번호가 빠른 손님부터 초밥을 먹습니다. 각 손님이 초밥을 몇 개 먹는지 구해야 합니다. 

 

우선순위 큐로 문저를 풀었습니다. 우선순위 큐를 2개 사용했습니다. 

첫 번째 우선순위 큐는 (초밥 번호, 손님 번호)로 이루어져 있습니다. 초밥 번호가 작은 순으로 나오면 초밥 번호가 같다면 손님 번호가 작은게 나옵니다.

두 번째 우선순위 큐는 제공되는 초밥을 담은 것으로 작은 번호 먼저 나옵니다. 

 

초밥을 제공하는 우선순위큐에서 꺼내서 제공합니다. 초밥 번호가 같으면 첫 번째 큐에서 꺼내고 손님 번호에 해당하는 배열에 +1을 합니다. 만약 제공하는 초밥이 첫 번째 우선순위큐의 초밥 보다 크다면 큐를 계속 큐를 비워냅니다. 

 

 

소스 코드

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

/*
회전초밥
https://www.acmicpc.net/problem/28107

(초밥 번호, 손님 번호) 우선순위 큐 만듬

 */

public class Main {

    static int n;
    static int m;
    static PriorityQueue<Customer> customers;
    static PriorityQueue<Integer> susis;
    static int[] answer;

    public static void main(String[] args) 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());

        customers = new PriorityQueue<>();

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int number = Integer.parseInt(st.nextToken());
            while(number-->0) {
                int susi = Integer.parseInt(st.nextToken());
                customers.add(new Customer(susi, i));
            }
        }

        answer = new int[n];

        st = new StringTokenizer(br.readLine());
        susis = new PriorityQueue<>();
        while (m-->0) {
            susis.add(Integer.parseInt(st.nextToken()));
        }

        while (!susis.isEmpty()) {
            int susi = susis.poll();

            while (!customers.isEmpty() && customers.peek().susi < susi) {
                customers.poll();
            }

            if (!customers.isEmpty() && customers.peek().susi == susi) {
                Customer c = customers.poll();

                // System.out.println(susi + " " + c.susi + " " + c.number);

                answer[c.number] += 1;
            }
        }

        for (int i = 0; i < n; i++) {
            System.out.print(answer[i] + " ");
        }

    }

    
    // 스시 번호 오름차순, 스시 번호 같으면 손님 번호 오름차순
    public static class Customer implements Comparable<Customer> {
        int susi;
        int number;

        Customer(int susi, int number) {
            this.susi = susi;
            this.number = number;
        }

        public int compareTo(Customer customer) {
            if (this.susi == customer.susi) {
                return this.number - customer.number;
            }
            return this.susi - customer.susi;
        }
    }

}

 

 

 

 

또 다른 문제 풀이

백준 숏코드에서 본 풀이 입니다. 

초반 번호 갯수만큼 deque를 만듭니다. 그리고 손님들이 초밥을 주문할 때 deque에 초밥 번호에 손님들 번호를 저장합니다. 해당하는 초밥이 들어오면 deque에서 꺼내서 정답 배열에 저장합니다. 

 

 

 

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

/*
회전초밥
https://www.acmicpc.net/problem/28107

주문 받는 형식
스시 번호에 맞게 주문한 손님들 번호를 저장
스시가 차례대로 주어질 때 이것을 참조하여 손님에게 제공
 */

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        Deque<Integer>[] orders = new ArrayDeque[200001];
        for (int i = 0; i < 200001; i++) orders[i] = new ArrayDeque<>();

        int[] answer = new int[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            while(k-->0) {
                orders[Integer.parseInt(st.nextToken())].add(i);
            }
        }
        st = new StringTokenizer(br.readLine());
        while(m-->0) {
            int susi = Integer.parseInt(st.nextToken());
            if (!orders[susi].isEmpty()) answer[orders[susi].pollFirst()] += 1;
        }

        for (int i = 0; i < n; i++) System.out.print(answer[i] + " ");
    }

}