백준 11866 요세푸스 문제 0

❌ 백준 11866 요세푸스 문제 0

오답.
큐를 쓰라는데 어디에다가 써야될지 감이 오지 않았다.

처음에 생각했던 풀이는 k의 간격으로 1~N의 배열을 계속 돌면서 결과배열 안에 있는 숫자는 건너뛰고, 도착한 숫자를 결과배열로 넣는 방식이었다.

대충 생각해도 오래걸릴만한 풀이였다.

계획을 다 짜고 보니 이 풀이는 좀 아닌거 같다는 생각이 들어서 버렸다.

그렇게 비슷한 풀이를 생각해봤지만, 전부 오래걸리는데다가 여전히 큐를 활용하지 않는 풀이였다.

결국은 알고리즘 책의 큐를 다룬 챕터를 참고했는데, 공교롭게도 첫번째 예제가 요세푸스 문제였다.

크게 두 과정으로 나뉜다.

1) 맨 앞의 요소를 맨 뒤로 보낸다. 이것을 k-1번 반복한다.
2) 1번이 끝난 시점의 제일 첫 원소를 뽑는다.

이게 다다.
너무 허무했고, 왜 이 풀이는 생각해지 못했을까 싶었다.

이것만 알면 코드는 어려울 것이 없었다.

import sys
import collections

n,k = map(int,sys.stdin.readline().split())

result = [] # 결과값들을 순서대로 담는 배열

queue = list(range(1,n+1)) # 1~n까지의 배열

queue = collections.deque(queue) # 위 배열을 deque로 변환

while len(result) != n : # 결과값에 1~n이 전부 채워질 때까지
    
    for i in range(k-1) :
        queue.append(queue.popleft()) # 맨 앞의 요소를 맨 뒤로 보낸다. k-1번 반복.
        
    result.append(queue.popleft()) # 반복문이 끝나면 제일 앞에 있는 원소를 뽑아서 결과로 넣는다.

mystr = ', '.join([str(item) for item in result]) # 결과값의 원소만 뽑아서 문자열로 변환

print('<'+mystr+'>') # 결과값을 양식에 맞게 출력