[Python] BOJ 18258번: 큐 2

18258번: 큐 2

 

어려운 문제는 아니지만, 참고할만한 내용이 다수 있어서 가져왔다.

---

1차 시도

코드

import sys

INs = list(map(lambda x: x.split(), sys.stdin.readlines()[1:]))
Q = []

for IN in INs:
    cmd = IN[0]
    if cmd == 'push':
        Q.append(IN[1])
    elif cmd == 'pop':
        print(-1 if len(Q) < 1 else Q.pop(0))
    elif cmd == 'size':
        print(len(Q))
    elif cmd == 'empty':
        print(1 if len(Q) < 1 else 0)
    elif cmd == 'front':
        print(-1 if len(Q) < 1 else Q[0])
    elif cmd == 'back':
        print(-1 if len(Q) < 1 else Q[-1])

native Python의 list 구조로 생성하여 접근했다.

 

문제는 list.pop 연산의 시간 복잡도가 O(n)이라는 것.

(이전 포스팅의  [Python] BOJ 10815번: 숫자 카드 (tistory.com)의 TimeComplexity - Python Wiki 링크 참조)

 

list는 구조가 단순하여 메모리 비용은 적지만, 이러한 수정 작업에는 매우 큰 비용을 치뤄야 한다.

이를 개선하기 위해 collections 패키지에서 deque(double-ended queue) 자료구조의 popleft 메소드를 활용했다.

** 추가로 len 연산의 시간 복잡도는 1이라는 점은 기억해둘만한 것 같다.

---

2차 시도

코드

from collections import deque
import sys

INs = list(map(lambda x: x.split(), sys.stdin.readlines()[1:]))
Q = deque()

for IN in INs:
    cmd = IN[0]
    if cmd == 'push':
        Q.append(IN[1])
    elif cmd == 'pop':
        print(-1 if len(Q) < 1 else Q.popleft())
    elif cmd == 'size':
        print(len(Q))
    elif cmd == 'empty':
        print(1 if len(Q) < 1 else 0)
    elif cmd == 'front':
        print(-1 if len(Q) < 1 else Q[0])
    elif cmd == 'back':
        print(-1 if len(Q) < 1 else Q[-1])

코드의 이론적인 시간 복잡도는 입력 크기에 비례한 O(n)으로 이상이 없는 것 같은데,
Python3 환경에서는 시간 초과 문제로 통과되지 않았다.

PyPy3에서는 코드과 통과된 이유가 무엇일까?

자세한 내용을 찾아보았다.

---

PyPy - Features | PyPy

PyPy - Features

1. 기존 Python의 CPython을 RPython(Restricted-)로 대체했다. 

2. RPython은 JIT(Just-in-Time) Compile을 지원한다.

3. 반복적인 작업에 더 유리하다.

 

** 이외에도 기존 Python 문제점에 대한 검색 결과들이 있는데,

파편화된 정보만 있어서 나중에 정리된 내용을 참고해야겠다.