[BOJ](Python) 2998번 : 8진수 / deque 주의할 점

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

2998번: 8진수

import sys
from collections import deque
input = sys.stdin.readline
dic = {'000':'0', '001':'1', '010':'2', '011':'3', '100':'4', '101':'5', '110':'6', '111':'7'}
temp = input().rstrip()
dq = deque()
for i in temp:
    dq.append(i)
number = len(dq) % 3
if number == 1:
    dq.appendleft('0')
    dq.appendleft('0')
elif number == 2:
    dq.appendleft('0')
dq = [i for i in dq]
ans = ''; i = 0
while i <= len(dq)-3:
    ans += dic[''.join(dq[i:i+3])]
    i += 3
print(ans)

0을 왼쪽에 삽입해야는 함으로 일반적인 리스트를 사용하여 dq.pop(0)을 하게 되면 O(n)이므로 매우 시간이 느리다.

deque를 사용하면 appendleft를 통해 O(1)로 첫 번째 요소에 0을 넣을 수 있으므로 매우 효율적이다.

dq = deque()
for i in temp:
    dq.append(i)
number = len(dq) % 3
if number == 1:
    dq.appendleft('0')
    dq.appendleft('0')
elif number == 2:
    dq.appendleft('0')

 

deque는 슬라이싱이 불가능하다. 따라서, dq의 요소를 하나씩 불러와서 리스트로 만들어주고 슬라이싱을 한다.

dq = [i for i in dq]

 

주의할 점: Python에서 deque를 불러오는 방법은 두가지가 있다.

1. from queue import deque

2. from collections import deque

 

하지만 백준에서 from queue import deque를 할 경우 코드가 완벽하더라도 컴파일 에러가 발생하고 문제를 틀리게 된다. 따라서 무조건 2번을 이용해 deque 모듈을 불러와야 한다!

 

백준, 자주 틀리는 요인, https://www.acmicpc.net/blog/view/70