백준 21756 - 지우개 (파이썬)

https://www.acmicpc.net/problem/21756

풀이

주어진 N개의 숫자가 1부터 N까지의 정수로 구성된 큐에서 특정 규칙에 따라 제거되며 마지막 남는 숫자를 출력하는 문제이다.

1. 초기 큐 구성
   1. deque를 활용하여 1부터 N까지의 숫자를 큐에 추가한다.
2. 반복적인 삭제 과정
   1. 큐의 길이가 1보다 클 동안 계속 반복한다
   2. 현재 큐의 길이를 n이라 할때, 처음부터 시작하여 짝수 번째 인덱스에 있는 원소를 제거한다.
   3. 홀수번째 인덱스에 있는 원소는 큐의 뒤로 이동시킨다.
3. 마지막 남은 숫자 출력

시간복잡도 분석

1. 모든 원소를 한번씩 탐색함 → O(N)

최적화 코드

이 문제의 패턴을 관찰하면, 2의 거듭제곱 형태로 숫자가 감소함을 알 수 있다.

즉, N이하의 가장 큰 2의 거듭제곱 수가 정답이 된다.

N = int(input())
power = 1
while power * 2 <= N:
    power *= 2
print(power)

예를 들어

• N = 6일 때 → 1 2 3 4 5 6 → 2 4 6 → 4 6 → 4
• N = 10일 때 → 1 2 3 4 5 6 7 8 9 10 → 2 4 6 8 10 → 4 8 → 8

즉, 마지막 남는 숫자는 N 이하의 가장 큰 2^k 값.

코드

# 백준 21756 - 지우개
# 분류 : 큐
 
from collections import deque
 
N = int(input())
 
queue = deque()
for i in range(1, N + 1) :
    queue.append(i)
 
while len(queue) > 1 :
    n = len(queue)
 
    for i in range(n) :
        if i % 2 == 0 :
            queue.popleft()
        else :
            queue.append(queue.popleft())
 
print(queue[0])