[S1] 백준 28107번 회전초밥 C++ 큐

리뷰

 

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

큐를 20만개를 쓴다는게 메모리 적으로 괜찮은가 생각이 들었지만 제한이 1024MB이므로 그냥 했더니 AC를 받았다.

 

 

전역 변수

• n, m : 손님의 수 n, 요리의 수 m
• cnt : 손님이 먹은 초밥의 개수를 저장할 정수형 배열
• q : 각 초밥을 먹고 싶어하는 사람의 큐 배열, 1번 손님부터 우선 순위가 주어진다.

 

함수

없음

 

 

문제풀이

1. n, m값을 입력 받고 1번 손님부터 n번 손님까지 반복문을 실행한다.
2. 해당 손님이 먹고 싶어하는 초밥의 개수를 정수형 변수 c에 입력받고, c번의 반복문을 실행한다.
3. 먹고 싶어하는 초밥의 번호를 정수형 변수 s에 입력 받고, s인덱스 큐에 손님의 번호 i를 추가해 준다.
4. m개의 초밥을 순회하기 위해 m번의 반복문을 실행해 준다.
5. 요리사가 만든 초밥의 번호를 정수형 변수 s에 입력 받고, s인덱스 큐가 비었는지 체크해 준다.
6. 비지 않았다면 s인덱스 큐에서 요소를 빼네 해당 손님의 cnt를 증가시킨다.
7. 모든 작업을 마친 후 1번 손님부터 n번 손님까지 반복문을 실행한다.
8. cnt에 저장된 각 손님이 초밥을 먹은 개수를 공백으로 구분하여 출력해 준다.

 

참고 사항

vector를 통해 동적으로 큐를 할당해도 되지만 최악의 케이스가 들어오면 어차피 동일하니 배열로 해주었다.

 

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;

int n, m;
int cnt[100001];
queue<int> q[200001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		int c; cin >> c;
		while (c--) {
			int s; cin >> s;
			q[s].push(i);
		}
	}

	while (m--) {
		int s; cin >> s;
		if (!q[s].empty()) {
			cnt[q[s].front()]++;
			q[s].pop();
		}
	}

	for (int i = 1; i <= n; ++i) cout << cnt[i] << " ";
}