Kotlin] 백준 1158번 풀이

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

 

흔한 요세푸스 문제입니다.

 

요세푸스 문제의 첫번째 난관은 없어진 인덱스에서 다음 기점으로 세서 삭제한다는 점이 있습니다. 즉, 죽인(?) 인덱스를 기억해야합니다.

두 번째는 그래서 그 인덱스를 저장한다고 해서 인덱스를 끊임없이 + 하다보면 언젠가는 배열의 크기를 넘어버리는 시점이 옵니다. 그럼 처음으로 다시 돌아와 세야만 합니다.

 

따라서, 인덱스의 시작 지점을 어디로 보느냐가 중요합니다. 저는 초기값과 죽은 인덱스를 -1로 보고 올라가는 숫자에서 -1을 제외한 값을 인덱스에 더해가며 값을 올렸습니다. 

생각해보십쇼. 케이스 중에 7 1의 문제가 있다고 가정합니다.

[1 2 3 4 5 6 7]의 배열에서 요세푸스의 첫번째 숫자를 삭제한다 했을때 0을 삭제합니다.

즉, 1이 올라가도 0 + (-1 + 1)로 0이 됩니다.

7 2여도 마찬가지입니다. 7 2이기 때문에 두 번째 숫자를 삭제해야합니다. 배열로 치면 1이죠. 0 + (-1 + 2) = 1이 됩니다. 

그러면 

[1 3 4 5 6 7] 이 남습니다. 죽인 인덱스는 1입니다. 여기서  다시 1 + (-1 + 2) = 2가 됩니다. 그럼 4를 삭제하게 됩니다.

[1 3 5 6 7] 이렇게 남게 되겠죠. 빼진 숫자는 리스트를 새로 선언해 순서대로 채워넣기만 하면 됩니다.

 

따라서 이를 생각해서 식을 세우면

 

fun main() {
    question1158()
}

fun question1158() {
    val case = readln().split(" ").map { it.toInt() }

    val list = (1 .. case[0]).toMutableList()
    val josephus = mutableListOf<Int>()
    
    var index = 0
    while (list.size > 0) {
        index = if(index + (case[1] - 1) < list.size) {
            index + (case[1] - 1)
        } else {
            (index + (case[1] - 1)) % list.size
        }
        josephus.add(list.removeAt(index))
    }

    println("<${josephus.joinToString(", ")}>")
}