[파이썬] 백준 2164 : 리스트는 큐로 이용하면 안된다.

[파이썬] 백준 2164 : 리스트는 큐로 이용하면 안된다.

 

오답 - 시간초과

n = int(input())

nums = []
for i in range(1,n+1):
    nums.append(i)

while len(nums) > 1:
    nums.pop(0)
    nums.append(nums.pop(0))
    # print(nums)


print(nums[0])

반복도 한번만 쓰고, 기본 내장함수로 쉽게 풀어냈구나 싶었다.

하지만 시간초과가 났다.

 

 

 

찾아보니 첫번째 요소 pop에 대해서

리스트는 O(n), Deque는 O(1) 이 걸린다.

Deque	List

구조 및 원리를 살펴보자.

 

 

리스트는 첫번째 원소를 제거하는 - pop(0) 을 하면 남아있던 원소들이 한칸씩 이동해서 O(n) 시간이 걸린다.

( pop()의 경우 뒤에서 원소를 삭제하기 때문에 O(1)이 걸린다. )

내부적으로 list는 고정된 사이즈의 메모리 형태이다.

List

 

 

 

 

덱(Deque: A Double-ended Queue)는 양 끝 원소 추가삭제를 지원한다.

내부적으로 deque는 이중연결리스트(double-linked list) 형태로 구현되어있다. 

Deque

 

 

정답

n = int(input())

from collections import deque
dq = deque()

for i in range(1,n+1):
    dq.append(i)

while len(dq) > 1:
    dq.popleft()
    dq.append(dq.popleft())

print(dq[0])

 

 

 

 

+ 참고

https://www.acmicpc.net/blog/view/70

Python과 Pypy

• BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
• 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 Pypy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
• 두 수를 입력받고 나서 비교할 때는 반드시 int로 변환을 합시다. 문자열의 비교는 사전 순 비교이기 때문에, 3은 10보다 작지만 "3"은 "10"보다 큽니다.
• is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
• list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 이외에도 O(N)이 걸리는 list 연산이 굉장히 많습니다. https://wiki.python.org/moin/TimeComplexity
• 위의 이유로, list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 collections.deque를 써야 합니다.
• 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.
• 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
• 두 개의 int를 나누면 float이 됩니다. int(a/b) 말고 a//b를 쓰는 것이 훨씬 안전합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.

 

+ 참고

https://wellsw.tistory.com/122

[파이썬] 덱 vs 리스트 속도 차이? (deque vs list speed 차이)