[백준] 1158 요세푸스 문제 (실버4) / 큐

문제요약

나의 코드 및 설명 - 리스트를 이용한 풀이

• 1부터 n까지의 수를 저장한 <num_li> 리스트를 생성하고, 정답으로 출력할 요세푸스 순열을 저장할 리스트를 <ans>로 초기화한다.
• <num_li> 의 요소가 다 제거될 때 까지 반복하는 while문을 생성한다.
  num_plan_idx :  제거되어야 할 인덱스
  if len(num_li) == 0 : 만약 num_list에 저장된 요소가 하나도 없으면 반복문을 탈출한다. (다음 작성한 코드에서 len(num_li)로 나누어야 하는 경우가 나오는데, 0으로 나눠지는 것을 방지한다.)
  num_li의 인덱스 num_plan_idx의 값을 pop() 함수를 통해 제거하고, ans에 저장한다. 그 다음, 다음에 수행될 반복에 대해 num_plan_idx 를 갱신해주어야 하는데, num_li 의 요소가 하나 삭제가 되었으므로 다음 반복 시 ans에는 인덱스 num_plan_idx + k 에서 1을 빼준 인덱스 <num_plan_idx + (k-1)> 의 값이 ans에 저장되어야 한다. 인덱스의 범위가 리스트의 길이 - 1을 초과하면 안되므로 len(num_li)의 나머지에 해당하는 값을 num_plan_idx 의 값으로 갱신시킨다.

n, k = map(int, input().split())

num_li = list(range(1,n+1))
ans = []
num_plan_idx = k-1
while num_li:
    ans.append(num_li.pop(num_plan_idx)) 
    if len(num_li) == 0:
        break
    else:
        num_plan_idx = (num_plan_idx + (k-1)) % len(num_li)

print("<",end="")
for i in range(len(ans)):
    if i == len(ans)-1:
        print(ans[i],end="")
    else:
        print("{}{}".format(ans[i],", "),end="")
print(">")

다른 코드 및 설명 - queue 를 이용한 풀이

• queue = deque(range(1, n+1)) : deque() 를 통해 큐를 생성한다.
• for _ in range(k-1) : k-1 만큼 수행하는 반복문을 생성한다.
  queue.append(queue.popleft()) : idx = 0 ~ k-2 까지 큐에서 제거하고, 큐의 뒤에 추가한다. 이렇게 함으로써 제거해아할 큐의 요소가 가장 첫 번째 인덱스로 오게된다.
  첫 번째 인덱스의 값을 제거하고 ans에 저장한다.

from collections import deque
n, k = map(int, input().split())
queue =  deque(range(1, n + 1))
ans = []

while queue:
    for _ in range(k-1):
        #[1,2,3,4,5,6,7] 에서 k = 3일때, 
        #queue 에서 뺀 1,2 를 queue의 제일 마지막에 놓음으로써
        #빼야될 수를 가장 첫 번째 요소에 둔다.
        #[3,4,5,6,7,1,2] 
        queue.append(queue.popleft())
    ans.append(queue.popleft())

print(str(ans).replace('[','<').replace(']','>'))

피드백

리스트를 사용하여 간단하게 구현할 수 있어서 만족했었지만, 큐를 이용한 풀이를 보고 깜짝 놀랐다. 어떻게 이런 생각을 할 수 있는걸까.. 제거해야할 수가 k라면, k-1 까지 popleft() 메서드를 통해 제거하고 큐의 뒤에 붙인 후, 제거해아할 수인 k를 큐의 가장 첫 번째 인덱스로 놓는다.. 이러한 문제가 주어졌을 때 리스트로 문제를 해결하는 것 보다, 큐로 문제를 해결하면 더 간단하고 빠를 수 있다는 것을 항상 명심하자.