[Python] 백준 11866번 - 요세푸스 문제 0

📖 문제

11866번: 요세푸스 문제 0

 

🔎 풀이

큐를 활용하는 문제입니다. deque를 선언하고, popleft 함수를 이용하면 0번째 인덱스의 원소를 O(1)에 추출할 수 있습니다. 앞에서부터 추출하면서, 해당 원소가 K번째라면 결과 리스트에 추가해줍니다. 아니라면 기존 리스트에 다시 맨 뒤로 추가합니다.

 

popleft 함수의 비용이 O(1)이더라도, 결과적으로는 전부 탐색해야하기 때문에 생각보다 시간이 오래 걸리는 문제였습니다. 오히려 pop(i)를 이용해 원하는 K번째 요소를 우선적으로 뽑는 것이 더 효율이 좋습니다. 아래 코드는 큐를 이용하였습니다.

 

💻 코드

import sys
import collections
input = sys.stdin.readline

N, K = map(int, input().split())
# 남은 숫자들의 배열
nums = collections.deque([x for x in range(1, N+1)])
result = []

cnt = 0
while nums:
    cnt += 1
    # 앞에서부터 pop
    num = nums.popleft()
    # 만약 K번째라면 결과 리스트에 추가
    if cnt == K:
        result.append(num)
        cnt = 0
    # K번째가 아니라면 다시 nums 리스트에 추가
    else:
        nums.append(num)

print('<', end='')
print(*result, sep=', ', end='')
print('>')