[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로 만들면 더 쉽다는 사실을 알게되었다.
다음에는 이러한 사실을 기반으로 문제를 풀어나가보자.

좋은 웹페이지 즐겨찾기