백준 28107번 회전초밥 Java

: ) YOUNG·2024년 9월 26일
1

알고리즘

목록 보기
401/417
post-thumbnail

백준 28107번 회전초밥 Java

https://www.acmicpc.net/problem/28107

문제



생각하기


  • 자료구조 문제이다.

1번 손님부터 N번 손님 순서대로 그 초밥을 받게 된다.

만약 먼저 초밥을 받는 손님이 초밥을 먹을 경우, 뒤의 손님들은 해당 초밥을 먹을 수 없다.

손님들은 다양한 초밥을 먹고 싶어하기 때문에 각 종류의 초밥은 최대 한 번만 먹는다.

각 손님의 주문 목록에 적힌 초밥 종류는 모두 다르다.

목록에 적히지 않은 초밥을 받는다면, 그 초밥은 반드시 먹지 않는다.

각 손님이 먹게 되는 초밥의 개수를 구해보자.



동작



결과


코드



import java.io.*;
import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N, M;
    private static HashMap<Integer, ArrayDeque<Integer>> sushiMap;

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

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() throws IOException {
        StringBuilder sb = new StringBuilder();

        int[] ans = new int[N + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int j = 0; j < M; j++) {
            int temp = Integer.parseInt(st.nextToken());
            ArrayDeque<Integer> que = sushiMap.get(temp);
            if (que == null || que.isEmpty()) {
                continue;
            }

            int waiter = que.poll();
            ans[waiter]++;
        }
        
        for (int j = 1; j <= N; j++) {
            sb.append(ans[j]).append(' ');
        }
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        sushiMap = new HashMap<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int count = Integer.parseInt(st.nextToken());

            for (int j = 0; j < count; j++) {
                int temp = Integer.parseInt(st.nextToken());

                if (sushiMap.get(temp) == null) {
                    sushiMap.put(temp, new ArrayDeque<>());
                }
                sushiMap.get(temp).add(i + 1);
            }
        }
    } // End of input()
} // End of Main class


0개의 댓글