[Kotlin] 백준 9519 : 졸려

문제 링크

9519번: 졸려

---

문제 해설

눈을 \(x\)번 깜박인 결과로부터 원래 단어를 찾아내야 한다. 처음에는 단순히 문제에서 주어진 연산을 \(x\)번 역수행해서 구해보려고 했는데 입력의 최대치가 10억인 것을 보고 시간 초과가 날게 뻔해서 다른 방법을 찾아보기로 했다.

 

예제로 주어진 테스트 케이스를 직접 돌려보면 일종의 규칙이 있다는 것을 볼 수 있다.

0은 최초 입력으로 주어진 단어이고, 각 회차는 이전 단어에서 문제에서 주어진 연산을 역수행한 결과이다. 첫번째 예제의 경우에는 5번을 주기로 같은 사이클이 반복되는 것을 확인할 수 있고, 세번째 예제의 경우에는 3번을 주기로 같은 사이클이 반복되는 것을 확인할 수 있다.

 

이러한 성질을 이용해서 사이클을 찾아서 문제를 푸는 방법을 사용했다. 이를 위해 입력 순서가 보장되는 MutableSet(= LinkedHashSet)을 사용해서 중복된 단어가 들어올 때까지, 즉 사이클이 완성되어 새로운 단어가 시작 단어와 같아질 때까지 문제에서 주어진 연산을 역수행하는 반복문을 수행했다.

 

사이클이 완성되었다면 반복문에서 탈출하여 \(x\)를 사이클의 크기로 나눈 나머지에 해당하는 단어를 출력하면 된다.

Code

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val word = readLine()
    val tailStart = word.lastIndex - if (word.length % 2 == 1) 1 else 0
    val set = mutableSetOf<String>().apply { add(word) }
    while (true) {
        val prev = set.last()
        val sb = StringBuilder()
        for (i in prev.indices step 2) sb.append(prev[i])
        for (j in tailStart downTo 0 step 2) sb.append(prev[j])
        if (!set.add(sb.toString())) break
    }
    println(set.toList()[n % set.size])
}