[백준] 2164번: 카드2 (sol.2)

풀이시간: 14분

1. 나의 풀이

from collections import deque

card_q = deque()

for i in range(1, int(input()) + 1):
    card_q.append(i)

while len(card_q) > 1:
    card_q.popleft()
    second_top = card_q.popleft()
    card_q.append(second_top)

print(card_q[0])

• 카드 덱의 맨 앞과 맨 뒤에서 작업이 일어나므로 큐로 풀이
• 먼저 카드덱을 만들고 문제의 상황 순서대로 작성
• 맨 앞 카드 제거, 그 뒤 카드 pop 이후 반환값 받아 카드 덱 맨 뒤에 추가

2. 또다른 풀이

from collections import deque

N = int(input())
dq = deque(range(1, N + 1))

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

print(dq.popleft())

일반 배열(리스트)로 풀면 안되는 이유

• 하나 남을 때까지 반복해야 함: N-1
• 맨 앞의 값을 삭제하고 그 뒤의 값을 삭제하고 맨 뒤에 삽입해야함: 3*O(N)
• Q((N-1) * 3N) = Q(N^2)

3. 보완할 것

• 생략하여 변수를 줄일 수 있는 부분은 줄여 메모리 공간을 최대한 아끼자