[백준/Python] 2164번 - 카드 2

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())
q = deque([i for i in range(1, n+1)])

while len(q)!=1:
  q.popleft()
  q.append(q.popleft())

print(q[0])

 

큐로 풀면 되는 아주 간단한 문제다

 

시간 복잡도

deque는 double-linked list로 구현되어 있음

그래서 양 끝의 요소의 추가/삭제가 O(1)을 만족

 

반면, Python의 list는 fixed size memory blocks(array)로 구현되어 있음. 링크드 리스트처럼 보이지만 고정된 사이즈의 메모리를 갖는 array

따라서 리스트의 마지막 원소 삭제는 O(1)이지만, 첫번째 원소를 삭제하면 삭제 후 모든 원소를 앞으로 이동시키기 때문에 시간 복잡도가 O(n)

 

여기서는 deque를 써서 추가/삭제에 별다른 시간 복잡도는 없고, 마지막 원소 하나가 남을 때까지 순회를 하는 시간복잡도만 존재

=> O(n)

 

다른 사람 풀이

- 수학적으로 풀었다... 근데 이해는 안됨

n,m = int(input()), 1
while m<n: # O(logn)
    m *= 2
print(2*n-m)

m은 n이상의 최소 2의 제곱수(ex. (n,m) = (6,8), (7, 8), (8, 8), (9, 16))

여기서 2를 곱해준 횟수만큼이 제일 아래로 이동하는 숫자의 개수와 동일(ex. 8=2^3, 즉 3개의 숫자가 뒤로 이동함)

 

참고 사이트

https://wellsw.tistory.com/122