[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)))
느낀점
역시 로직이 생각이 나지 않으때는 손으로 써보면서 규칙을 찾는것이 좋은 것 같다.
'Study > Algorithm' 카테고리의 다른 글
[BOJ] 1149 - RGB거리 (0) | 2019.04.21 |
---|---|
[BOJ] 2579 - 계단 오르기 (0) | 2019.04.20 |
[BOJ] 1463 - 1로 만들기 (0) | 2019.04.20 |
[BOJ] 9095 - 1, 2, 3 더하기 (0) | 2019.04.19 |
[BOJ] 2839 - 설탕 배달 (0) | 2019.04.19 |