백준 2164번 카드2

■ 처음에 시간초과 떴던 코드

N = int(input())

L= [(i+1) for i in range(N)]

while len(L)>1:
        L.pop(0)
        L.append(L.pop(0))

print(L[0])

 

■ 제출코드

위에 코드를 이용해서 한 50까지 출력해놓고 패턴을 찾아서 코드를 작성했다. 

N보다 작은 2의 제곱수 중 가장 큰 값을 k라고 했을 때, (N - k) * 2 가 답이다.

N = int(input())
s = 1

while True:
    if (N == 1 or N == 2) :
        print(N)
        break
    
    s *= 2
    if N <= s:
        print(int(((N-(s/2)) * 2)))
        break

 

■ 다른 풀이

다름 사람들을 살펴보니 deque를 활용해서 첫 번째 제출했던 코드를 구현해서 제출했다.

[Python] 파이썬 데크(deque) 정리

<데이터 추가 및 제거 시 시간복잡도>

- list : O(n)

- daque : O(1)   # 아주 빠르다!