Algorithm
[파이썬] 백준 1158번: 요세푸스 문제
bbomi
2023. 11. 19. 02:16
https://www.acmicpc.net/problem/1158
1158번: 요세푸스 문제
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)
www.acmicpc.net
n, k = map(int, input().split())
a = list(range(1, n+1))
from collections import deque
que = deque(a)
new = []
i = 0
while que:
que.append(que.popleft())
i += 1
if i % k == 0:
a = que.pop()
new.append(a)
if len(que) == 1:
new.append(que.pop())
break
print('<' + ', '.join([str(x) for x in new]) + '>')
deque를 사용해서 푸는 방법입니다:
1. n값을 받은 후 1부터 n까지의 a라는 list 생성 -> deque로 받습니다.
2. new라는 빈 list 생성 후, i = 0 으로 지정합니다.
3. que로 while문을 돌린 후, que 맨 앞의 값을 뒤로 빼냅니다. 이후 i+=1을 해줍니다.
- 만약 i가 k로 나눠진다면. que에서 해당 값을 빼낸 후 new에다 넣어줍니다
(예: i=3 일 경우에 que의 맨 왼쪽 값이 3이 되고, k=3일 경우 나눠지니까 해당 값을 빼냅니다).
- que에 마지막 한개 값이 남으면 new에다가 넣고 while문을 break 해줍니다.
4. 포맷에 맞춰 출력합니다.
=> <3, 6, 2, 7, 5, 1, 4> 와 같은 포맷이니, list값을 str로 바꿔주고 양쪽에다 < > 를 붙입니다.