백준 1158번: 요세푸스 문제 (Python)

 

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

1158번: 요세푸스 문제

---

Level: Silver IV

Solved By: Queue

 

파이썬에서는 Queue를 사용하기 위해서 deque을 사용합니다. queue를 사용하지 않는 이유는 파이썬에서 제공하는 queue는 멀티스레드를 위해 동기화 과정을 거치기 때문에 문제풀이용으로는 좋지 않습니다.

그래서 deque을 사용하여 문제를 풀 수 있으며, 아래와 같이 가져올 수 있습니다.

from collections import deque

그리고, deque에서는 아래와 같이 원소를 push, pop 하며 양 옆으로 가능합니다.

dq = deque()

dq.append(element)
dq.pop()
dq.appendleft(element)
dq.popleft()

 

문제를 풀이하는 방식은 덱에 1부터 N까지 push를 해두고, 반복되는 count가 K가 될 때마다 결과 값을 담을 list에 담아줍니다. count가 K가 되지 않는 반복에서는 원처럼 덱을 사용하기 위해 pop을 시킨 원소를 뒤에 push 합니다.

import sys
from collections import deque

N, K = map(int, sys.stdin.readline().split())

queue = deque([i for i in range(1, N + 1)])
res = []
cnt = 0

while len(queue) > 0:
    temp = queue.popleft()

    queue.append(temp)
    cnt += 1
    if cnt == K:
        res.append(temp)
        queue.pop()
        cnt = 0
        
print("<", end='')
for i in range(0, len(res)):
    print(res[i], end = '')
    if i != len(res) - 1:
        print(", ", end='')
print(">", end='')