[BOJ] 1158 - 조세퍼스 문제

[BOJ] 1158 - 조세퍼스 문제

문제

문제

조세퍼스 문제는 다음과 같다.

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)

출력

예제와 같이 조세퍼스 순열을 출력한다.

예제 입력

7 3

예제 출력

<3, 6, 2, 7, 5, 1, 4>

문제 해결

링크드 리스트로 BOJ 에서 유명한 조세퍼스 문제를 풀어보겠다. 링크드 리스트에 관한 포스팅은 다음 포스팅에서 좀 더 자세히 다루겠다. 여러가지 풀이 방식이 있겠지만 나는 다음 index 를 찾아내는 공식을 세워 문제를 해결하였다.

예시에서 주어진 7 3 을 이용하여 규칙을 찾아보자. 현재 배열의 길이를 L, 현재 인덱스를 I, 라고 했을때 사람을 한명씩 제거해보자.

n = 7, k = 3
[1, 2, 3, 4, 5, 6, 7]     L: 7, I: 0
[1, 2, 4, 5, 6, 7]        L: 6, I: 2    > 3
[1, 2, 4, 5, 7]            L: 5, I: 4    > 6
[1, 4, 5, 7]            L: 4, I: 1     > 2
[1, 4, 5]                L: 3, I: 3     > 7
[1, 4]                    L: 2, I: 2     > 5
[4]                        L: 1, I: 0     > 1
[]                        L: 0, I: 0    > 4 -> 조건 탈출

위에 상황을 가지고 한번 공식을 세워 보자.

(0 + 2) % 7 = 2
(2 + 2) % 6 = 4
(4 + 2) % 5 = 1
(1 + 2) % 4 = 3
(3 + 2) % 3 = 2
(2 + 2) % 2 = 0
(0 + 2) % 1 = 0
(현재 인덱스 + (k-1)) % 현재 배열 길이 = 다음 인덱스

사실 이 공식이 바로 나온 것이 아니라 사람의 수를 더 늘려보고 K의 수도 늘려본 결과 이 식이 완성되었다. 공식을 구했으니 링크드 리스트처럼 찾은 인덱스의 -1의 next 값에 현재 인덱스 +1의 value를 넣기만 하면 된다. 이 때 주의할 점은 현재 인덱스가 배열의 마지막 요소여서 범위를 넘는 값을 연결하는 것만 조심하면 된다.

1. 림크드 리스트처럼 현재 자신의 값(v) 과 자기 다음 값(n)을 가지고 있는다.
2. "(현재 인덱스 + (k-1)) % 현재 배열 길이 = 다음 인덱스" 공식을 이용하여 인덱스를 알아낸다.
3. 현재 인덱스의 -1 해당 하는 값의 n에 현재 인덱스의 +1 의 v를 대입 (단 +1 한 값이 현재 배열의 크기를 넘지 않게 처리를 해주어야 한다.)

이제 조건이 전부 완성되었으니 코드로 작성해보겠다.

python 코드

arr = []
new_arr = []

n, k = map(int, input().split())
index = 0
for i in range(1, n+1):
    arr.append({"v" : i, "n" : (i+1) % n})

while len(arr) > 0 :
    index = (index + k - 1) % len(arr)
    arr[index - 1]["n"] = arr[(index + 1) % len(arr)]["v"]
    new_arr.append(str(arr.pop(index)["v"]))

print("<%s>" %(", ".join(new_arr)))

느낀점

역시 로직이 생각이 나지 않으때는 손으로 써보면서 규칙을 찾는것이 좋은 것 같다.