요세푸스 문제: Kotlin과 Queue로 고전적인 퍼즐 풀기

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

문제

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

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

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

Queue로 Josephus 문제를 해결하기 위해 모든 사람을 대기열에 추가하는 것으로 시작할 수 있습니다.

그런 다음 모든 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
}