요세푸스 문제: Kotlin과 Queue를 사용한 고전적인 퍼즐 풀기

요세푸스 문제는 수세기 동안 존재해 온 고전적인 퍼즐입니다.
그것은 유대-로마 전쟁 중에 유사한 전략을 사용했다고 알려진 고대 유대 역사가 요세푸스의 이름을 따서 명명되었습니다. 
이 퍼즐에서 n명의 사람들이 원 안에 서 있고 한 사람만 남을 때까지 k번째 사람을 모두 제거해야 합니다. 

문제 진술

1에서 n까지 번호가 매겨진 원 안에 n명의 사람이 있다고 가정합니다. 
1인부터 시작해서 한 사람만 남을 때까지 k번째 사람마다 제거해야 합니다. 예를 들어 서클에 10명의 사람이 있고 k=3인 경우 다음 사람을 제거합니다.

1, 4, 7, 10, 5, 2, 9, 6, 3

마지막으로 남은 사람은 8번째 사람입니다.

큐(Queue)를 사용하여 요세푸스 문제를 해결하기 위해 모든 사람을 대기열에 추가하는 것으로 시작할 수 있습니다.

 
그런 다음 모든 k번째 사람을 대기열에서 빼고 다시 큐 끝에 다시 추가하고 또다시 k 번째 사람을 큐에서 제거할 수 있습니다.
대기열에 한 사람만 남을 때까지 이 작업은 계속 됩니다.

 

하기는 kotlin으로 작성된 코드 입니다.

fun josephus(n: Int, k: Int): Int {
    val queue = LinkedList<Int>()
    for (i in 1..n) {
        queue.add(i)
    }
    while (queue.size > 1) {
        repeat(k - 1) {
            queue.add(queue.remove())
        }
        queue.remove()
    }
    return queue.first
}