10845: 큐 - Python

beaver.zip·2024년 12월 11일

백준

[알고리즘] 백준

목록 보기

30/45

문제

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

풀이 1 (오답 - 시간 초과)

from collections import deque

N = int(input())
dq = deque()

for _ in range(N):
    cmd = input()
    if cmd[:4] == "push":
        dq.append(int(cmd[5:]))
    elif cmd == "pop":
        print(dq.popleft() if dq else -1)
    elif cmd == "size":
        print(len(dq))
    elif cmd == "empty":
        print(0 if dq else 1)
    elif cmd == "front":
        print(dq[0] if dq else -1)
    else:
        print(dq[-1] if dq else -1)

이전에 푼 문제(카드 2)에서 알게된 deque을 사용했다.
그러나 시간 초과가 발생했다.

풀이 2 (정답)

from collections import deque
import sys

input = sys.stdin.readline
N = int(input())
dq = deque()

for _ in range(N):
    cmd = input().strip()
    if cmd == "front":
        print(dq[0] if dq else -1)
    elif cmd == "back":
        print(dq[-1] if dq else -1)
    elif cmd == "pop":
        print(dq.popleft() if dq else -1)
    elif cmd == "size":
        print(len(dq))
    elif cmd == "empty":
        print(0 if dq else 1)
    else:
        dq.append(int(cmd[5:]))

풀이 1에서 입력과 조건문의 순서를 개선했다.

N(1 ≤ N ≤ 10,000)개 줄을 입력받아야 하므로 input()을 sys.stdin.readline()으로 수정했다.
또한 명령이 push인지 검사하려면 slicing을 사용해야 하므로, 가장 마지막 조건으로 옮겼다.
(그러나 GPT o1이 말하기를, 일반적으로 cmd[:4]과 같은 slicing 연산은 매우 빠른 연산으므로 이 정도 변경으로 인한 시간 단축은 극히 미미하다고 한다.)

추가적으로, GPT가 dq[0], dq[-1]의 시간 복잡도가 O(n)이라고 하길래 front, back 함수를 다음과 같이 고쳐서 제출했다.

    if cmd == "front":
        if dq:
            x = dq.popleft()
            print(x)
            dq.appendleft(x)
        else:
            print(-1)
    elif cmd == "back":
        if dq:
            x = dq.pop()
            print(x)
            dq.append(x)
        else:
            print(-1)