14일차 - 식당 메뉴 ( 백준 - 26043번 )

26043 : 식당메뉴

---

문제

여러 명의 학생이 식사하기 위하여 학교 식당을 향해 달려가고 있다. 학교 식당에 도착한 학생은 식당 입구에 줄을 서서 대기한다. 학교 식당에 먼저 도착한 학생이 나중에 도착한 학생보다 식당 입구의 앞쪽에서 대기한다. 식사는 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 

6
1 2 1
1 1 1
2 1
1 3 2
2 2
2 2

예제 출력 1 

2 3
1
None

---

풀이

문제를 읽었을 때 처음에 들어온 학생이 먼저 메뉴를 받고 나가기 때문에 큐로 풀어야한다고 생각했다.

 

1. 우선 식당 정보의 수를 n으로 받아오며 학생의 번호와 원하는 메뉴를 넣을 큐를 만들어 준다.

n = int(sys.stdin.readline())

q = deque()

2. 좋아하는 메뉴를 먹은 학생 목록 A와  좋아하지 않는 메뉴를 먹은 학생 목록 B, 식사를 하지 못한 학생 목록 C 를 넣을 빈 리스트를 만든다.

A = [] 
B = [] 
C = []

3. 식당의 n개 정보를 info라는 리스트에 저장해준다.

for _ in range(n):
    info = list(map(int, sys.stdin.readline().split()))

4. 만약 info[0]의 값이 1이면 학생에 대한 정보인 학생번호, 원하는 메뉴번호 가 들어올 것이고 2이면은 메뉴에 대한 정보인 메뉴 번호가 들어올 것이다.

if info[0] == 1:
    student = info[1]
    menu = info[2]
    q.append((student, menu))  ## 큐에 학생번호와 원하는 메뉴번호 저장

elif info[0] == 2:
    menu = info[1]
    if q:
        student, hope_menu = q.popleft()
        if current_hope == menu:
            A.append(student)  # 원하는 메뉴를 받았으면 A그룹에 학생번호 추가
        else:
            B.append(student)  # 원하는 메뉴가 아니면 B그룹에 학생번호 추가

5. q에 남아있는 학생정보를 확인하여 정보가 있다면 C그룹에 학생번호를 저장해준다.

while q:
    student, menu = q.popleft()
    C.append(student)  # 남아있는 학생들은 원하는 메뉴를 끝까지 받지 못함

6. 문제에서 오름차순으로 출력하라고 했기 때문에 오름차순 정렬을 해준 뒤, 리스트가 비어있지 않다면 공백으로 연결하여 출력하고 비어있다면 None을 출력한다.

A.sort()
B.sort()
C.sort()

print(" ".join(map(str, A)) if A else "None")
print(" ".join(map(str, B)) if B else "None")
print(" ".join(map(str, C)) if C else "None")

-  A와B, C는 리스트 형식이기 때문에 " ".join(map(str, A)) 을 사용하여 공백으로 구분된 문자열로 출력하도록 함.

---

제출코드 

from collections import deque
import sys

n = int(sys.stdin.readline())

q = deque()
A = []
B = []
C = []

for _ in range(n):
    info = list(map(int, sys.stdin.readline().split()))
    if info[0] == 1:
        student = info[1]
        menu = info[2]
        q.append((student, menu))
    elif info[0] == 2:
        menu = info[1]
        if q:
            student, hope_menu = q.popleft()
            if hope_menu == menu:
                A.append(student)
            else:
                B.append(student)

while q:
    student, menu = q.popleft()
    C.append(student)

A.sort()
B.sort()
C.sort()

print(" ".join(map(str, A)) if A else "None")
print(" ".join(map(str, B)) if B else "None")
print(" ".join(map(str, C)) if C else "None")