[백준/python] 1158번 요세푸스 문제

 

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

1158번: 요세푸스 문제

 

문제분석

N명의 사람이 원을 이루면서 앉아있을 때, K번째 사람을 모든 사람이 제거될 때까지 계속 반복하는 문제이다.

 

코드

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

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

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

 

문제풀이

1. 스택과 큐의 기능을 가진 deque 모듈을 import 한다.

2. n과 k를 입력받고, 1부터 n까지의 숫자를 queue에 넣어준다.

3. while문의 조건은 queue안에 숫자가 하나도 없기 전까지로 하고, for문은 k를 범위로 정한다. queue의 왼쪽 값을 popleft로 빼서 queue에 다시 append 함으로써 제거해야 할 K번째 수를 제일 왼쪽에 둔다.

4. K번째 수를 제거해서 정답 배열인 answer에 추가한다.

5. while문이 끝났으면, answer []를 <>으로 교체해주면서 출력하고 종료한다.