[백준/BOJ] 11866번: 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

해설

처음에는 큐를 이용하여 문제를 풀으려 했지만 큐에는 원하는 인덱스를 지우는 메소드가 없어 LinkedList를 사용했다.

우선 StringBuilder를 만들어 <를 넣어준다.

이후 리스트의 크기가 1이 될 때까지 반복문을 돌리며 StringBuilder에 list[index]를 넣어주고, 그 위치의 값을 지운다.

k번째마다 반복되는 것이므로 (index + k) % list.size를 해주면 된다.

마지막으로 반복문을 빠져나와 list.poll()과 >를 StringBuilder에 넣어주면 된다.

소스 코드

import java.lang.StringBuilder
import java.util.*

fun main() {
    val st = StringTokenizer(readLine())
    val sb = StringBuilder()
    val n = st.nextToken().toInt()
    val k = st.nextToken().toInt() - 1
    val list: LinkedList<Int> = LinkedList()
    repeat(n) { list.add(it + 1) }
    sb.append("<")
    var idx = k
    while(list.size != 1) {
        sb.append("${list[idx]}, ")
        list.removeAt(idx)
        idx = (idx + k) % list.size
    }
    sb.append("${list.poll()}>")
    println(sb.toString())
}