파이썬 2164번 카드2 - list와 deque의 시간복잡도 & 0~N 리스트 만들기

앞에서 나가고 뒤로 들어오길래 

음 큐 쓰면 되겠다 했다.

 

import sys
N=int(sys.stdin.readline())
q=[]
for i in range(1, N+1):
    q.append(i)
    
while len(q)>1:
    q.pop(0)
    temp=q.pop(0)
    q.append(temp)
    
print(q[0])

 

append 저 모냥으로 해도 되나? 했는데 

그것도 그렇고 list도 그렇고 시간 초과

일단 저 append는

N= int(input())
q = list(range(1, N+1))

로 하면 훨씬 간단하다.

 

그리고 보통 이런 문제에선 import deque쓰지 않나? 근데 앞뒤에서 양방향 출입은 필요 없는데 꼭 그래야 하나? 고민했다.

 

찾아보니 데크는 양 끝 요소의 append와 pop이 압도적으로 빠르다고 한다.

양끝 요소에 접근하여 삽입 또는 제거 동작을 할 때,  

일반적인 리스트는 O(n) 소요. 그에 반해 데크(deque)는 O(1)만 걸린다. 시간 면에서 데크가 압도적 효율을 자랑한다.

 

그래서 deque를 이용한 풀이는

from collections import deque

n = deque(range(1, int(input())+1,))
while len(n) != 1:
    n.popleft()
    n.rotate(-1)
print(n[0])

rotate를 사용하면 원소 회전 가능.

deque.rotate(1) 이러면 deque의 원소를 오른쪽으로 한바퀴 돌린다.

deque.rotate(2)면 오른쪽으로 두바퀴.

 

-1을 넣으면 왼쪽으로 한바퀴.