백준 11866 풀이 (요세푸스 문제 0, 큐)

이번 문제를 처음 읽었을 때는 상당히 쉽다고 생각했다. 코드로 로직을 작성하는데에는 문제가 없었지만, 문제는 왜 큐를 사용해야 하는지 이해를 하지 못했다. 그래서 코드는 금방 짰으나 문제가 의도하는 바를 이해하지 못했다.

우선은 내가 짠 코드이다.

from collections import deque
n, k = map(int, input().split())
tmp = [i for i in range(1,n+1)]
ys = []
count = 1
i = 0
while len(tmp) != 0:
    if count == k:
        print(i, tmp)
        ys.append(tmp[i])
        count=1
        tmp.pop(i)
        if i == len(tmp):
            i = 0
        continue
    count+=1
    if i == len(tmp)-1:
        i=0
        continue
    i+=1
print("<", end='')
print(str(ys)[1:-1], end='')
print(">", end='')

코드는 간단하다. count를 세면서 count가 k일때의 인덱스의 값을 리스트에 넣고 마지막에 모두 출력해준다.

문제는 풀었으나 의도를 파악하지 못하여 고수들의 코드를 확인해보았다.

진짜 너무 신기했다.

 

우선 큐에 모든 값을 넣는다.

그리고 index 0부터 시작하여 3번째 값이 나오기 전 값들 2개를 큐 뒤로 보낸다.

그리고 index 1부터 시작하여 3번째 값이 나오기 전 값들 2개를 큐 뒤로 보낸다.

그리고 index 2부터 시작하여 3번째 값이 나오지 전 값들 2개를 큐 뒤로 보낸다.

......

마지막으로 index n-k 부터 시작하여 3번째 값이 나오기 전 값들 2개를 큐 뒤로 보낸다.

그러면 <3,6,2,7,5,1,4> 값의 요세푸스값을 구할 수 있다.