[알고리즘] 백준 2164 : 카드2 - S4

2023.04.06 풀이

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

n=int(input())
queue=deque(range(1, n+1))

for i in range(n-1):
    queue.popleft()
    k=queue.popleft()
    queue.append(k)

print(queue[0])

• 아래는 첫번째 시도 : 시간초과

import sys
input=sys.stdin.readline

n=int(input())
arr=list(range(1, n+1))

for i in range(n-1):
    arr.remove(arr[0])
    k=arr[0]
    arr.remove(k)
    arr.append(k)

print(arr[0])

다른 풀이

input = int(input())
square = 2

while True:
    if (input == 1 or input == 2):
        print(input)
        break
    square *= 2
    if (square >= input):
        print((input - (square // 2)) * 2)
        break

import math
n=int(input())
a=math.floor(math.log2(n))
if n==2**a:
    print(n)
else:
    ans=(n-2**a)*2
    print(ans)

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

check point

• 속도 측면에서 list보다 deque가 유리 (append,pop이 압도적으로 빠름)
  • list : O(n)
  • deque : O(1)
• 따라서 deque는 push/pop 연산이 많을 경우 사용
• ratate() : 이동시키는 큐 함수