[백준] 1158번 요세푸스 문제 - Python / 알고리즘 기초 1/2 - 자료구조 1

---

---

---

💡문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

---

💭 접근

1. 만약 예제와 같이 k = 3 이라면 3번 째 수를 선택한 뒤, 이 수를 list에서 제외시키기 때문에 pos 변수에 k가 아닌 k-1 씩 더해줘야한다.

2. 이때 pos가 list의 크기보다 작을 땐 기존의 arr list에서 stack list로 옮겨준다.
   -> stack.append(arr(pos))

3. 이후, pos가 list의 크기보다 커지면 pos %= len(arr)

   ex) 예제
   pos = 2, stack = [3], arr = [1, 2, 4, 5, 6, 7], len(arr) = 6
   pos = 4, stack = [3, 6], arr = [1, 2, 4, 5, 7], len(arr) = 5
   pos = 6 > 5, (pos %= len(arr), pos = 1)
   stack = [3, 6, 2], arr = [1, 4, 5, 7] len(arr) = 4
   ...

---

🔥 내가 작성한 코드

n, k = map(int, input().split())
arr = [i for i in range(1, n + 1)]
pos = 0
stack = []

for _ in range(n):
    pos += k - 1
    if pos >= len(arr):
        while pos >= len(arr): # 처음엔 len(arr)만큼 빼야한다고 생각했다.
            pos -= len(arr)
    stack.append(arr.pop(pos))

print(str(stack).replace('[', '<').replace(']', '>'))

---

📒 코드

n, k = map(int, input().split())

origin = [i for i in range(1, n + 1)]
ans = []
pos = 0

for _ in range(n):
    pos += k - 1

    if pos >= len(origin): # 나머지 연산으로도 구현 가능!
        pos %= len(origin)
    
    ans.append(origin.pop(pos))

print(str(ans).replace('[', '<').replace(']', '>'))

---

💭 후기

k가 아닌 k-1 씩 더해주는 것과 pos가 list 크기보다 커졌을 때를 잘 생각해보면 풀릴 문제.
항상 맞았다고 넘어갈게 아닌 더 나은 코드가 있는지 찾아보고 숙지하자.

str(ans).replace('[', '<').replace(']', '>')

replace 함수를 알게되었다. 문자열 문제 풀때 유용하게 쓰일 것 같으니 잘 기억하자!

---

🔗 문제 출처

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

---