[Python]BeakJoon Algorithm 11866번 요세푸스 순열
[문제출처] https://www.acmicpc.net/problem/11866
위의 문제를 deque를 이용하여 풀었다.
k번째의 값을 요세푸스 순열이라 말하는 y List에 입력하여준다.
이렇게 되면 앞의 (k-1)개의 값들을 다시 뒤로 배열해 주어야 하며 이 과정에서 popleft를 통해 (k-1)개의 값들을 deque의 뒷부분에 입력한다.
이후 a의 deque안에 남아있는 개수가 k보다 작아지게 되면 k%len(a)=0일때와 아닐때를 구분하여본다.
이렇게 되면 k%len(a)=0일때는 deque의 값이 pop되며 아닐시에는 (k%len(a)-1)번째 index값이 pop되며 요세푸스 순열의 List에 들어가게 된다. 하지만 여기서 문제가 발생이 된다.
Deque는 index접근이 안된다.
그러므로 우리는 이에 해당하는 값을 다시 blank의 List로 옮겨 거기서 다시 값을 추출하였다.
반복문을 계속할 떄 blank를 계속적으로 clear시켜주면서 마지막까지 요세푸스 순열을 찾아낸다.
from collections import deque
n,k=map(int,input().split())
a=deque()
y=[]
blank=[]
for i in range(n):
a.append(i+1)
for i in range(n):
blank.clear()
if len(a) >=k:
for j in range(k):
b=a.popleft()
if j==(k-1):
y.append(b)
else:
a.append(b)
else:
c=k%len(a)
if c==0:
b=a.pop()
y.append(b)
else:
c-=1
for i in range(c+1):
t = a.popleft()
blank.append(t)
for i in range(c):
a.append(blank[i])
b=blank[c]
y.append(b)
print("<",end='')
for i in range(n):
if i==(n-1):
print(y[i],end='')
else:
print(y[i],end=', ')
print(">")
이 코드를 다 짜고난후 que를 while을 통하여 원 que로 만들면 더 쉽다는 사실을 알게되었다.
다음에는 이러한 사실을 기반으로 문제를 풀어나가보자.
Author And Source
이 문제에 관하여([Python]BeakJoon Algorithm 11866번 요세푸스 순열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@elecheung/PythonBeakJoon-Algorithm-11866번-요세푸스-순열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)