백준 18258번- '큐 2' (PYTHON 풀이)

문제:

스택을 배울 때 같이 배우는 자료구조가 큐이다. 이전에 스택은 구멍이 하나라 후입선출법을 따른다고 말했다.

큐는 구멍이 두개라 공정한 자료구조이다. 즉, 들어가는 입구 나가는 입구가 따로 있어서 선입선출법을 따른다.

오늘 문제는 이러한 큐를 구현하는 코드이며, 큐에 대한 개념을 잘 모르더라도 시간 복잡도만 유의해서 해당 설명대로 풀면 쉽게 풀 수 있다.

 

풀이:

import sys
N = int(sys.stdin.readline())
li = []

for i in range(N):
    a = sys.stdin.readline().split()
    if a[0] == 'push':
        li.append(a[1])
    elif a[0] == 'pop':
        if not li:
            print(-1)
        else:
            po = li.pop(0)
            print(po)
    elif a[0] == 'size':
        print(len(li))
    elif a[0] == 'empty':
        if not li:
            print(1)
        else:
            print(0)
    elif a[0] == 'front':
        if not li:
            print(-1)
        else:
            print(li[0])
    elif a[0] == 'back':
        if not li:
            print(-1)
        else:
            print(li[-1])

처음 코드를 이렇게 작성했다. 정말 단순히 설명 그대로 구현했다. 시간 초과를 대비해서 sys를 import해서 진행했으나 이 역시도 시간초과가 발생하였다. 원인이 궁금해서 게시판을 뒤져보니 pop(0)을 쓰게 되면 맨 앞에 있는 값이 빠지기 때문에 O(n)의 시간 복잡도를 가져서 시간 초과가 나는 것 같다는 댓글을 보았다. 그럼 pop을 쓰면 안되나 싶어 del li[0]로 작성해 시도해보았으나 동일하게 시간 초과가 발생했다.

어떻게 풀어야 시간 단축이 되는지 모르겠어서 게시판을 뒤져보았는데 deque라는 것이 있는 것을 처음 알게 되었다. deque는 스택과 큐를 쉽게 사용할 수 있는 도구라고 한다. 이를 반영해 코드를 작성하면 아래와 같다.

 

import sys
from collections import deque

N = int(sys.stdin.readline())
q = deque()

for i in range(N):
    a = sys.stdin.readline().split()
    if a[0] == 'push':
        q.append(a[1])
    elif a[0] == 'pop':
        if q:
            print(q.popleft())
        else:
            print(-1)
    elif a[0] == 'size':
        print(len(q))
    elif a[0] == 'empty':
        if q:
            print(0)
        else:
            print(1)
    elif a[0] == 'front':
        if q:
            print(q[0])
        else:
            print(-1)
    elif a[0] == 'back':
        if q:
            print(q[-1])
        else:
            print(-1)

collections는 파이썬에 내장되어있는 모듈 중 하나로, 설치할 필요 없이 바로 사용이 가능하다.

기존에 리스트 형태는 높은 시간복잡도를 가질 수 밖에 없는데 deque는 그것보다 더 빠르게 스택과 큐를 구현할 수 있다.

사용 방법은 리스트에서 사용하는 것과 비슷하다. 우선 시간 초과 방지를 위해 sys를 그대로 사용하고, for문을 그 수만큼 돈다.

그 후 push가 들어올 경우, 숫자를 큐에 추가하고, pop일 경우엔 popleft를 활용해 앞의 수를 제거하고 출력한다. 나머지는 코드를 보면 그대로 어떤 로직인지 이해할 수 있는 수준이라 설명은 생략하겠다.

 

 

스택에서는 sys를 사용해서 시간 초과 없이 풀었던 것으로 기억하는데, 큐도 만만하게 봤다가 시간을 좀 더 썼다. 그래도 deque라는 기능을 알게 되어서 앞으로 잘 써먹을 수 있을 것 같다!