1. 문제 설명
[문제]
여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 1인분씩 준비된다. 식사 1인분이 준비되면 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식당으로 들어가서 식사를 시작한다. 식사를 시작한 학생은 항상 식사를 마친다.
학교 식당에서는 두 가지 메뉴가 제공되고 각각의 학생은 두 가지 메뉴 중에서 본인이 좋아하는 메뉴를 결정한 상태다. 학생이 학교 식당에 도착하고 식사가 준비되는 n개의 정보가 저장된 S가 주어진다. S에 저장된 첫 번째 정보부터 n번째 정보까지 순서대로 처리한 경우, 본인이 좋아하는 메뉴를 먹은 학생 목록 A와 본인이 좋아하지 않는 메뉴를 먹은 학생 목록 B와 학교 식당에 도착하였으나 식사를 하지 못한 학생 목록 C를 출력하자.
S에 저장된 n개의 식당 정보는 아래 두 가지 유형으로 구분된다. 첫 번째가 유형 1, 두 번째가 유형 2다.
-
1 a b: 학생 번호가 양의 정수 a이고 좋아하는 메뉴 번호가 양의 정수 b인 학생 1명이 학교 식당에 도착하여 식당 입구의 맨 뒤에 줄을 서기 시작한다.
-
2 b: 메뉴 번호가 양의 정수 b인 식사 1인분이 준비되어 식당 입구의 맨 앞에서 대기 중인 학생 1명이 식사를 시작한다.
식사 1인분이 준비될 때는 식당 입구에서 대기 중인 학생이 항상 존재한다. 식당 입구에 줄을 서서 대기하였으나 식사가 준비 안 된 학생은 식사를 못 한다.
[입력]
첫 번째 줄에 n이 주어진다.
두 번째 줄부터 n개의 줄에 걸쳐 한 줄에 하나의 정보가 주어진다. 각 정보는 유형 1, 2중 하나이다.
[출력]
첫 번째 줄에 학생 목록 A에 있는 학생 번호를 빈칸을 사이에 두고 오름차순으로 출력한다.
두 번째 줄에 학생 목록 B에 있는 학생 번호를 빈칸을 사이에 두고 오름차순으로 출력한다.
세 번째 줄에 학생 목록 C에 있는 학생 번호를 빈칸을 사이에 두고 오름차순으로 출력한다.
학생 목록에 학생이 없는 경우 학생 번호 대신 None을 출력한다.
[제한]
-
1 ≤ n ≤ 500,000
-
S에는 유형 1, 유형 2만 저장되어 있다.
-
1 ≤ a ≤ n, 모든 양의 정수 a의 값은 서로 다르다.
-
b는 1 또는 2이다.
[입출력 예]
첫 번째 1 2 1을 처리한 후, 대기 줄은 (2 1)이 된다. (2 1)에서 2는 학생 번호, 1은 좋아하는 메뉴 번호를 나타낸다.
두 번째 1 1 1을 처리한 후, 대기 줄은 (2 1) (1 1)이 된다. (1 1)에서 앞쪽 1은 학생 번호, 뒤쪽 1은 좋아하는 메뉴 번호를 나타낸다. 2번 학생이 앞쪽, 1번 학생이 뒤쪽에서 대기 중임을 나타낸다.
세 번째 2 1을 처리하면, 앞쪽에서 대기 중인 2번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 (1 1)이 된다. 2번 학생이 좋아하는 메뉴 번호는 1이고 먹은 음식도 1번이므로 학생 목록 A에 2번 학생을 추가한다.
네 번째 1 3 2를 처리한 후, 대기 줄은 (1 1) (3 2)가 된다. (3 2)에서 3은 학생 번호, 2는 좋아하는 메뉴 번호를 나타낸다. 1번 학생이 앞쪽, 3번 학생이 뒤쪽에서 대기 중임을 나타낸다.
다섯 번째 2 2를 처리하면, 앞쪽에서 대기 중인 1번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄은 (3 2)가 된다. 1번 학생이 좋아하는 메뉴 번호는 1이고 먹은 음식은 2번이므로 학생 목록 B에 1번 학생을 추가한다.
여섯 번째 2 2를 처리하면, 앞쪽에서 대기 중인 3번 학생이 대기 줄을 나와서 식사를 하므로 대기 줄에는 아무도 없다. 3번 학생이 좋아하는 메뉴 번호는 2이고 먹은 음식도 2번이므로 학생 목록 A에 3번 학생을 추가한다.
여섯 개의 정보를 모두 처리한 후 대기 줄에는 학생이 없으므로 식사를 못 하는 학생은 없다. 따라서 학생 목록 C에는 학생이 없다.
2. 풀이
import sys
from collections import deque
n = int(sys.stdin.readline().strip())
queue = deque()
A = []
B = []
C = []
for _ in range(n):
info = list(map(int, sys.stdin.readline().split()))
if info[0] == 1:
a, b = info[1], info[2]
queue.append((a, b))
elif info[0] == 2:
b = info[1]
student, favorite_menu = queue.popleft()
if favorite_menu == b:
A.append(student)
else:
B.append(student)
while queue:
C.append(queue.popleft()[0])
print(" ".join(map(str, sorted(A))) if A else "None")
print(" ".join(map(str, sorted(B))) if B else "None")
print(" ".join(map(str, sorted(C))) if C else "None")3. 회고
3-1. 문제 풀이 과정
문제 이해조차 못 했던 문제라서 어떻게 풀어야 할지 도무지 감도 안 잡히고 포기하고 싶었다. (1, 2, 1), (1, 1, 1) 이게 무슨 뜻인지 이해를 못했기 때문이다.
일단 학교 식당에서 학생들이 줄을 서고, 준비된 음식이 나오면 차례대로 먹는 상황이라는 것은 파악했다. 줄을 서는 순서대로 음식이 나가기 때문에 자료구조 중에서 큐를 이용하면 되었다.
가장 앞에 붙는 1과 2는 각각 학생이 줄을 서는 것과 식사하는 것을 의미하는 것을 이해했다. 만약 (1, 2, 1)이 입력된다면 학생 2가 메뉴 1을 먹기 위해 줄을 섰다는 것을 뜻한다. 그리고 (2, 1)이 입력되면 메뉴 1이 준비가 되었고 가장 먼저 줄을 선 학생 2가 해당 메뉴를 먹게 된다.
이렇게 해서 학생이 줄을 선 다음에 자신이 원하는 메뉴를 먹게 된 건지, 그렇지 않은 메뉴를 먹게 된건지, 메뉴가 준비되지 않아서 음식을 먹지 못한 학생을 구별하여 리스트에 저장한 다음에 마지막에 각각 출력하면 되는 나름 쉬운 문제였던 거 같다.
deque()를 이용해서 FIFO 대기열을 먼저 형성했다. 그리고 info라는 변수를 이용해서 3개의 숫자들을 받아오고 공백을 기준으로 쪼개었다. 가장 처음에 오는 숫자, 즉 info[0]이 1이면 큐에 (a, b) 형태로 info[1], info[2]를 저장했다.
info[0] == 2인 경우에는 메뉴가 나왔다는 의미이고 b가 메뉴를 뜻하므로 b == info[1]가 된다. 음식이 나왔으니 큐에 있는 (a, b)는 popleft()를 이용하여 삭제한다. 이때 자신이 원하는 메뉴를 먹었는지를 구분하여 리스트에 학생 번호를 저장한다.
info 때문에 헷갈렸지만 나름대로 정리하니 전혀 어렵지 않았다.
3-2. 새롭게 배운 내용
popleft():collections.deque자료구조에서 사용하는 메소드로, 큐의 맨 앞 요소를 제거하고 반환하는 역할을 한다. 해당 문제에서는 줄을 선 학생 중 가장 앞에 있는 사람을 꺼내는 동작을 구현할 때 사용되었다.
리스트의 pop()은 리스트에서 맨 앞 요소를 제거한다는 점에서 popleft()와 차이가 있으며, 소요 시간도 더 걸린다.
deque(): 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형이다. 스택처럼 사용해도 되고 큐처럼 사용 가능하다고 한다.collections.deque모듈에서deque를 생성한다.
3-3. 참고 자료
