[백준] 11866 요세푸스 문제 0 python 알고리즘 문제

문제 11866. 요세푸스 문제 0

1. 나의 코드와 발상 과정

from collections import deque

queue = deque()
answer = []
n, k = map(int, input().split())
for i in range(1, n+1):
    queue.append(i)

while len(answer) < n:

    for i in range(k-1):
        queue.append(queue.popleft())
    answer.append(queue.popleft())

print("<", end = "")
for i in range(n-1):
    print("%d, "%answer[i], end = "")
print(answer[-1], end="")
print(">")

예제 입력을 보고 순간 이해가 되지 않았다.

1~7번째의 사람이면 첫 번째 죽는 사람은 3번째 사람인데, 왜 6번째 사람이 1번으로 죽는 것인지에 대해 의문이었다.

그렇지만 잘못 이해했다는 것을 금방 알 수 있었다.

 

n번째 사람이 몇 번째 타임에 죽는 지를 출력하는 것이 아니라,

n차 타임에 몇 번째 사람이 죽는 지를 출력하는 것이다.

 

즉, 출력되는 문장은 인덱스가 n번째 차례, 원소가 죽은 사람(n번째에 앉은 사람)인 것.

 

덱을 활용해서 문제를 풀었다.

먼저 deque()을 선언한 queue에 1부터 n까지의 숫자를 집어 넣는다.

그다음 ans에 차례로 죽은 사람을 집어 넣을 것이다.

 

while문을 활용해 len(answer)가 n과 같아지면 탈출하도록 조건을 만든 후에,

그 다음 반복문의 range를 k-1까지로 해서, queue의 가장 왼편에 있는 원소를 출력해서 다시 queue의 오른쪽으로 쌓아준다.

그러면 k번째의 죽을 사람이 가장 왼편에 위치하게 되는데, 이때 popleft를 통해 뽑아낸 후 answer에 append 한다.

 

(for문을 쓸 필요 없기도 하다. 이 문제를 풀고 다음에 문제를 풀다가 rotate 함수를 보았는데, 그것을 쓰면 훨씬 편하다.)

 

그다음 출력문을 활용해서 출력 형식에 맞게 프린트를 해준다.

 

2. 아쉬운 점

문제 이해를 더 빠르고 정확하게 하는 방법을 연습해야 한다.

 

 

 

문제 출처

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