[백준 11866, 1158][파이썬] 요세푸스 문제

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

11866번: 요세푸스 문제 0

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

1158번: 요세푸스 문제

입력 값의 범위와 메모리 제한만 다르고 같은 문제이다.

 

처음에는 이 문제가 deque를 이용해서 푸는 문제인지 몰라서 리스트로 풀었다.

 

리스트의 길이가 변화함에 따라 바뀌는 idx 값의 규칙을 알아내서 풀었다.

 

<옛날 코드>

import sys 
k, n =map(int, sys.stdin.readline().split())
li=[i for i in range(1, k+1)]
idx = 0
print('<', end = '')
while len(li)>0:
    idx=(idx+n-1)%len(li)
    if len(li)!=1:
        print(li.pop(idx),end = ', ')
    else:
        print(li.pop(idx), end = '')
print('>', end = '')

문제는 해결했지만 좋은 방법은 아닌듯 하다.

 

그러다가 이 문제가 deque 유형에 속해있는 것을 보고 그냥 deque를 하면서 풀면 간단하다는 것을 깨달았다.

 

알고리즘은 단순하다.

 

그냥 k-1만큼 앞에서 pop하고 뒤에 append를 한 다음 앞에서 pop한 값을 리스트에 넣어준다.

 

이 과정을 deque가 빌 때까지 반복하면 된다.

 

<최종 코드>

import sys
from collections import deque
n, k = map(int, sys.stdin.readline().split())
d=deque()
res=[]
for i in range(1, n+1):
    d.append(i)
while len(d)!=0:
    for _ in range(k-1):
        d.append(d.popleft())
    res.append(d.popleft())
print('<', end='')
for i in range(len(res)):
    if i==len(res)-1:
        print(res[i],end='>')
    else:
        print(res[i], end=', ')

참고로 1168번 문제도 같은 요세푸스 문제인데 그 문제는 세그먼트 트리를 이용해서 풀 수 있는 문제이다.

 

나중에 세그먼트 트리를 풀 차례가 되면 한 번 풀어봐야겠다.