[Algorithm] 백준 18258번: 큐 2 | 덱(Deque) 이용

문제 출처: https://www.acmicpc.net/problem/18258

---

1. 결과

메모리 92936KB, 시간 1764ms

2. 풀이

이전에 풀었던 큐 문제에서 이번엔 시간제한이 추가되었다. 문제 설명에서는 시간 복잡도가 O(1)이어야 한다고 제시했다. 연결 리스트를 통한 큐는 비교적으로 삽입, 삭제 등의 연산에서 유리하다고 생각했기 때문에 이전에 연결 리스트로 구현한 큐 코드를 그대로 제출했다. 하지만 이 코드가 시간 초과가 발생했다. 최대한 메모리와 연산을 줄여서 구현한 연결 리스트와 큐인데도 시간 초과가 발생했다.

이전에 패키지 collections에서 deque라는 자료구조가 큐를 구현한 것이고, queue 라이브러리의 Queue보다도 연산이 빠르다는 것을 들었기 때문에 이번엔 deque를 통해 구현을 했다. 확실히 빨랐고, 시간 초과가 발생하지 않으며 맞았다.

이 문제를 맞았지만, 그래도 어떤 라이브러리나 패키지를 사용하지 않은 풀이에 대해 고민을 했는데, 아래 블로그의 글 링크가 sys 외에는 어떤 것도 임포트 하지 않고, 파이썬의 자료형 리스트를 통해 구현하고 있었다. 큐의 출구를 가리키는 인덱스 변수 하나만을 추가로 만들어서 구현했는데, 이런 방법과 아이디어를 나도 능숙하게 떠올릴 수 있도록 공부해야겠다고 생각했다.

- deque 없이 구현한 queue: https://chancoding.tistory.com/35

[Python] 백준 18258번 큐2 - deque안쓰고 풀기

import sys
from collections import deque

def main():
    N = int(sys.stdin.readline())
    dq = deque()
    for _ in range(N):
        command = sys.stdin.readline().split()
        if command[0] == 'push': dq.append(int(command[1]))
        elif command[0] == 'pop':
            if dq: print(dq.popleft())
            else: print(-1)
        elif command[0] == 'size': print(len(dq))
        elif command[0] == 'empty':
            if dq: print(0)
            else: print(1)
        elif command[0] == 'front':
            if dq: print(dq[0])
            else: print(-1)
        elif command[0] == 'back':
            if dq: print(dq[-1])
            else: print(-1)
    return

if __name__ == "__main__":
    main()