[백준 1158] 요세푸스 문제

 

🔒 문제

 

💭 생각의 흐름

라이브러리에서 CircularQueue 를 제공하거나

이미 구현해놓은 코드가 있다면 CircularQueue 안에서  iterator를 쓰면 좋겠다고 생각은 했지만

java, kotlin 에서 CircularQueue를 제공하지 않으므로

 

그냥 사이즈의 최대 크기를 넘어가는 시점에는 mod(%) 연산으로 index를 조정하는 방식을 택했다.

출력 결과에 '<' 꺾새와 ',' 콤마를 넣어줘야해서 StringBuilder 를 사용했다.

 

 

"특정 인덱스의 원소를 삭제한 이후엔 인덱스를  -1 해서 조정해야한다."

 

예를 들어 다음과 같은 상태라면

index	0	1	2	3
value	1	2	3	4

 

'3'번째 를 지운다는건 index '2'에 해당하는 원소 3을 지우는 것과 같다.

지우고 나서의 queue 상태는 다음과 같아진다.

 

index	0	1	2
value	1	2	4

 

index '2'에 해당하는 원소를 지웠다면 현재 index가 1을 가리키도록 하여 다음 loop의 순서에 맞게 동작하게 해야한다.

 

🔑 풀이 (Kotlin)

fun main() {
    val stringBuilder = StringBuilder()

    val (number , sequenceNumber) = readLine()!!.split(" ").map { it.toInt() }
    val numberQueue = LinkedList<Int>(Array<Int>(number){it+1}.toList())

    var index : Int = -1
    while (numberQueue.isNotEmpty()) {
        index = (index + sequenceNumber) % numberQueue.size
        stringBuilder.append(numberQueue.removeAt(index--)).append(", ")
    }

    with(stringBuilder) {
        // 맨 끝의 콤마, 공백을 삭제함
        this.deleteCharAt(this.length - 1)
        this.deleteCharAt(this.length - 1)
        this.insert(0, '<')
        this.insert(this.length, '>')
    }

    println(stringBuilder.toString())
}