백준 11866번 요세푸스 문제 0 파이썬

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

11866번: 요세푸스 문제 0

 

내 답안

from collections import deque

N, K = map(int, input().split())
q= deque([i for i in range(1, N + 1)])

print('<', end='')
while q:
    for i in range(K - 1):
        q.append(q.popleft())
    print(q.popleft(), end='')
    if q:
        print(', ', end='')
print('>')

---

 

queue 의 맨 앞에 있는 원소를 k-1번 뒤로 보내는걸 반복해준다.

그리고 k번째에 popleft() 를 통해 그 원소를 삭제해주고 바로 문자열로 출력해주는 프로그램을 짰다.

쉽게 보여준다면

1.  deque([1, 2, 3, 4, 5, 6, 7])
2.  deque([2, 3, 4, 5, 6, 7, 1])
3.  deque([3, 4, 5, 6, 7, 1, 2])
4.  deque([4, 5, 6, 7, 1, 2])

.
.
.
.
.

이런 과정을 반복한다. 

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

1158번: 요세푸스 문제

이 문제는 N의 경우가 5000개로 커졌을 때인데 위의 답을 적어도 시간 초과 없이 잘 된다.