백준 알고리즘 11866번: 요세푸스 문(Python)

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

11866번: 요세푸스 문제 0

---

문제 해결을 위한 과정

이 문제는 구현 유형의 문제로서 어려운 문제는 아니었지만 문제를 해결하는 데 있어서 생각하는 방식이 중요한 문제였습니다. 문제에서 주어진 예시를 해결해보겠습니다.

다음의 그림은 예시를 푸는 과정입니다. 이 예시에는 N은 7, K는 3입니다.

그림1. 3번째 3 출력

그림2. 3번째 6 출력

그림3. 3번째 2 출력

그림4. 3번째 7 출력

그림5. 3번째 5 출력

그림6. 3번째 1 출력 

그림7. 3번째 4 출력

---

문제 해결을 위한 팁

이 문제는 위의 그림을 자세히 살펴보면 알 수 있듯이 k번째 원소가 아닌 것들은 다시 뒤에 붙여서 해결한다는 점입니다. 따라서 관찰을 통해 큐를 구현하면 해결할 수 있음을 알 수 있습니다. 파이썬에서 큐 보다 효율적인 deque를 이용해 popleft(), append()를 이용해 해결할 수 있습니다.

---

소스코드

from collections import deque
 
n, k = map(int, input().split())
q = deque()
 
for i in range(1, n+1):
  q.append(i)
 
print("<", end="")
i = 0
while True:
  i += 1
  if i != k:
    v = q.popleft()
    q.append(v)
  else:
    v = q.popleft()
    if (q):
      print(v, end=", ")
      i = 0
    else:
      print(v, end=">")
      break