[10845] 큐

 

백준 Silver IV | 10845 | Python | 문제 링크

문제 설명

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.

출력

출력이 있는 명령에 대해서 출력을 한다.

입출력 예

입력	출력
15 push 1 push 2 front back size empty pop pop pop size empty pop push 3 empty front	1 2 2 0 1 2 -1 0 1 -1 0 3

 

나의 풀이

풀이 1 - 버그 6개 들어있던 첫 제출

from collections import deque
import sys
input = sys.stdin.readline
q = deque()
num = int(input())
result = []
for _ in range(num):
    line = list(input.split())

    if line[0] == "push":
        q.append(line[1])
    elif line[0] == "pop":
        val = q.popleft()
        result.append(int(val))
    elif line[0] == empty:
        if stack: result.append("0")
        else: result.append("1")
    elif line[0] == front:
        if not stack: result.append(int(q[0]))
        else: result.append(-1)
    elif line[0] == back:
        if not stack: result.append(int(q[len(q)-1]))
        else: result.append(-1)

print("\n".join(result))

스택 구현 문제(10828번)를 막 끝낸 직후였다. 큐 구현을 보자마자 "이건 그냥 스택이랑 똑같네"라는 생각이 들었다. 자료구조도 알고, deque도 알고, 명령어 목록도 스택과 거의 같았다.

제출하고 오답이 떴다. 다시 보니 버그가 한두 개가 아니었다.

버그 1 — input.split()에 괄호가 없다

line = list(input.split())

input을 sys.stdin.readline으로 재정의한 상태다. 즉 input은 함수다. 함수 자체에다 .split()을 호출하고 있으니 AttributeError가 난다. input().split()으로 써야 하는 자리에서 괄호를 빠뜨렸다.

스택 문제를 풀 때는 아마 제대로 썼을 텐데, 그걸 복붙하면서 괄호가 날아간 것 같다. 황당한 실수였다.

버그 2 — 빈 큐에서 popleft()를 그냥 호출한다

val = q.popleft()

큐가 비어있을 때 pop 명령이 들어오면 -1을 출력해야 한다. 그런데 아무 확인 없이 popleft()를 호출하고 있으니 IndexError가 난다.

버그 3 — 문자열 비교에 따옴표가 없다

elif line[0] == empty:
elif line[0] == front:
elif line[0] == back:

empty, front, back이 따옴표 없이 쓰여 있다. Python은 이걸 변수명으로 인식한다. 정의된 적 없는 변수니까 NameError다. 전부 "empty", "front", "back"으로 써야 한다.

"push"와 "pop"은 따옴표를 붙였으면서 나머지 세 개는 빠뜨렸다. 쓰다가 집중력이 떨어졌던 것 같다.

버그 4 — 큐가 q인데 stack이라고 쓴다

if stack: result.append("0")
if not stack: result.append(int(q[0]))

q를 써야 하는데 stack이라고 쓰여 있다. stack은 이 코드 어디에도 정의되지 않은 이름이다. 직전에 스택 문제를 풀었던 탓에 변수명이 그대로 남아있었다.

버그 5 — empty, front, back 조건이 전부 반전되어 있다

이게 제일 골치 아팠다.

empty 명령은 큐가 비어있으면 1, 아니면 0을 출력해야 한다. front와 back은 큐가 있을 때 값을 반환하고, 없을 때 -1을 반환해야 한다.

버그 4를 고쳐 stack을 q로 바꿔도, front 로직은 여전히 반대로 써져 있었다.

if not q: result.append(q[0])

큐가 비어있을 때 q[0]에 접근한다. IndexError가 나는 코드다. 조건이 완전히 뒤집혀 있었다.

버그 6 — result에 int와 str이 섞여 있다

result.append("0")
result.append(-1)
result.append(int(val))

어떤 곳에서는 문자열을 넣고, 어떤 곳에서는 정수를 넣는다. 마지막에 "\n".join(result)를 쓰면 int가 섞여 있다는 TypeError가 난다.

1차 수정으로 문법 오류를 잡았지만, empty / front / back 세 곳의 조건 반전 문제가 남아서 2차 수정까지 갔다. 삼항 연산자로 정리하고 나니 조건과 결과가 한 줄에 보였다. 조건을 반전시킬 여지가 줄어드는 게 느껴졌다.

풀이 2 - 최종 제출 코드

from collections import deque
import sys
input = sys.stdin.readline

q = deque()
num = int(input())
result = []

for _ in range(num):
    line = input().split()

    if line[0] == "push":   q.append(line[1])
    elif line[0] == "pop":   result.append(q.popleft() if q else -1)
    elif line[0] == "size":  result.append(len(q))
    elif line[0] == "empty": result.append(1 if not q else 0)
    elif line[0] == "front": result.append(q[0] if q else -1)
    elif line[0] == "back":  result.append(q[-1] if q else -1)

print("\n".join(map(str, result)))

풀이 3 - match-case 활용 (Python 3.10+)

import sys
from collections import deque
input = sys.stdin.readline

q = deque()
result = []

for _ in range(int(input())):
    cmd = input().split()

    match cmd[0]:
        case "push":  q.append(cmd[1])
        case "pop":   result.append(q.popleft() if q else -1)
        case "size":  result.append(len(q))
        case "empty": result.append(0 if q else 1)
        case "front": result.append(q[0] if q else -1)
        case "back":  result.append(q[-1] if q else -1)

print("\n".join(map(str, result)))

elif 체인보다 명령어별 분기가 눈에 잘 들어온다. 문자열 비교에 따옴표를 빠뜨리는 실수도 case 문법에서는 좀 더 자연스럽게 잡힌다. 실제로 따옴표 없이 case empty:라고 쓰면 Python이 바로 패턴 매칭 구문 오류를 잡아준다.

deque.popleft()는 O(1)이다. list.pop(0)은 O(n)이다. 리스트에서 앞 원소를 꺼낼 때마다 나머지 원소를 전부 앞으로 당겨야 하기 때문이다. 큐를 구현할 때 deque를 써야 하는 이유가 여기에 있다.