[C++] BOJ 28107번: 회전초밥

문제

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

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

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

입력

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

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

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

$N+2$번째 줄에 요리되는 초밥의 종류를 나타내는 $M$개의 정수 $B_1,B_2,\ldots, B_M$이 공백으로 구분되어 순서대로 주어진다. ($1\leq B_i\leq 200\, 000$)

출력

한 줄에 $N$개의 정수 $C_1,C_2,\ldots C_N$을 공백으로 구분하여 출력한다. $C_i$는 $i$번 손님이 먹은 초밥의 개수를 의미한다.

---

접근 방법(1) - 메모리 초과

bool타입 2차원 배열을 선언해 ( array[i][j]에 대해 ) i번째 손님이 희망하는 초밥 j를 true로 할당하고자 했다.
이후 마지막 줄에서 입력받는 초밥에 대해 N명의 손님에 대해 for문을 통해 참 여부를 확인하면서 개수를 저장하고자 했다.
=> 입력 범위때문에 메모리 초과

접근 방법(2) - 맞았습니다

1. 큐를 선언하여 초밥 종류마다 손님을 저장했다. queue<int> sushi[]
2. 1차원 배열에 손님이 먹은 스시의 개수를 저장했다. int eaten[]

요리되는 초밥을 입력받을 때마다 해당하는 큐를 확인하고 비어있지 않다면 front를 pop함과 동시에 해당 손님이 먹은 스시의 개수를 증가시켰다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

#include <queue>
int n, m; // 손님의 수, 초밥 수
queue<int> sushi[200001]; // idx번째의 초밥을 선호하는 사람 목록을 넣을 것

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // 입력
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int k, a; // 해당 손님의 희망 초밥 개수, 초밥번호
		cin >> k;
		while (k--) {
			cin >> a;
			sushi[a].push(i); // a초밥을 i손님이 희망함
		}
	}
    
	int eaten[100001] = { 0 }; // idx번째 손님이 먹은 스시의 개수 저장
	while (m--) {
		int cur_sushi;
		cin >> cur_sushi;
		if (sushi[cur_sushi].empty()) continue; // 희망 손님이 없다면 continue 
        
		int guest = sushi[cur_sushi].front();
		eaten[guest]++;
		sushi[cur_sushi].pop();
	}
    // 출력
	for (int i = 0; i < n; i++) {
		cout << eaten[i] << " ";
	}
	return 0;
}