백준 28107번 회전초밥

문제

백준 28107번 회전초밥 링크

간단한 문제라고 생각한다. 특별한 알고리즘 기법이 들어가기보다는 문제 조건대로 큐를 사용해서 구현하면 된다.
또한 초밥 리스트 배열과 손님별 먹은 초밥 수 배열을 사용해야겠다는 아이디어만 있으면 충분히 풀 수 있다.

풀이 방법

1. 초밥 리스트 배열 만들기

먼저 그래프를 구현하는 것처럼 초밥 리스트 배열을 구현했다. 1 ~ N 손님들은 각 순서대로 우선순위가 있기 때문에 우선순위 큐 대신 그냥 큐를 사용했다. 따라서 초밥마다 먹을 사람을 링크드 리스트에 저장하는 형식이다.

// 초밥 리스트 배열 초기화
LinkedList<Integer>[] sushi = new LinkedList[200_001];
for (int i = 1; i <= 200_000; i++) {
    sushi[i] = new LinkedList<>();
}

2. 초밥 리스트 배열 채우기

이제 주어진 손님 리스트에 따라 초밥 리스트를 채운다.

// 초밥 리스트 배열 채우기
for (int i = 1; i <= N; i++) {
    st = new StringTokenizer(br.readLine());
    int dishes = Integer.parseInt(st.nextToken());
    for (int j = 0; j < dishes; j++) {
        int now = Integer.parseInt(st.nextToken());
        sushi[now].add(i);
    }
}

3. 요리사가 만든 초밥을 먹을 사람 구하기

이제 우선순위가 저장되었으므로 요리사가 초밥을 만들 때마다 초밥을 먹을 사람을 정해주어야한다. 따라서 요리사가 초밥을 만들면 초밥 리스트에서 해당 초밥의 리스트를 확인하여 사이즈가 0보다 크면 해당 사람을 리스트에서 삭제하고, 손님별 먹은 초밥 수 배열에서 해당 손님을 +1 한다.

// 요리사가 초밥을 만드는 과정
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= M; i++) {
    int now = Integer.parseInt(st.nextToken()); // 요리사가 현재 만든 초밥
    if (sushi[now].size() > 0) { // 초밥을 먹을 사람이 있으면
        int eatPerson = sushi[now].remove(0);
        eat[eatPerson]++;
    }
}

4. 각 사람이 먹은 초밥의 개수 출력하기

이제 손님별 먹은 초밥 수 배열을 순서대로 출력한다.

for (int i = 1; i <= N; i++) {
    sb.append(eat[i]).append(" ");
}

정답 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.StringTokenizer;

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

        // 손님 수와 초밥 수 입력받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken()); // 손님 수
        int M = Integer.parseInt(st.nextToken()); // 초밥 수

        // 손님별 먹은 초밥 수 배열 초기화
        int[] eat = new int[N + 1];
        // 초밥 리스트 배열 초기화
        LinkedList<Integer>[] sushi = new LinkedList[200_001];
        for (int i = 1; i <= 200_000; i++) {
            sushi[i] = new LinkedList<>();
        }

        // 초밥 리스트 배열 채우기
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int dishes = Integer.parseInt(st.nextToken());
            for (int j = 0; j < dishes; j++) {
                int now = Integer.parseInt(st.nextToken());
                sushi[now].add(i);
            }
        }

        // 요리사가 초밥을 만드는 과정
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= M; i++) {
            int now = Integer.parseInt(st.nextToken()); // 요리사가 현재 만든 초밥
            if (sushi[now].size() > 0) { // 초밥을 먹을 사람이 있으면
                int eatPerson = sushi[now].remove(0);
                eat[eatPerson]++;
            }
        }

        for (int i = 1; i <= N; i++) {
            sb.append(eat[i]).append(" ");
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}