9519번: 졸려

문제 출처 : https://www.acmicpc.net/problem/9519

 

언어 : Kotlin

 

문제 설명 :

선영이는 다가오는 COCI에 사용할 데이터를 만드느라 삼일동안 깨어있었다. 더 이상 데이터를 만들 수 없는 상황에 이르렀고, 심지어 선영이는 신경쇠약에 걸려 아무것도 제대로 보지 못하는 상황이 되었다.

선영이가 무엇인가를 읽다가 눈을 한 번 깜박하면 단어의 뒷 부분 절반이 앞 부분과 섞이게 된다. (길이가 홀수인 경우에는 뒷 부분의 길이가 짧다) 섞이는 방법은 아래와 같다.

마지막 글자가 첫 번째 글자와 두 번째 글자 사이로 이동한다.
뒤에서 두 번째 글자가 두 번째 글자와 세 번째 글자 사이로 이동한다.
뒤에서 k번째 글자는 앞에서부터 k번째와 k+1번째 글자 사이로 이동한다.
예를 들어, 선영이가 "abcdef"란 단어를 보다가 눈을 한 번 깜박이면, 단어가 "afbecd"가 된다. 여기서 한 번 더 깜박이면 "adfcbe"가 된다.

선영이는 한 단어를 쓰고난 이후에 눈을 X번 깜박였고, 처음에 작성한 단어가 무엇인지 궁금해졌다. X와 눈을 X번 깜박인 후에 선영이가 보고 있는 단어가 주어졌을 때, 원래 단어가 무엇이었는지 구하는 프로그램을 작성하시오.

 

입력 :

첫째 줄에 X(1 ≤ X ≤ 1,000,000,000) 가 주어지고, 둘째 줄에 X번 깜박인 후의 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 구간 [3,1000]에 포함된다.

 

출력 :

첫째 줄에 X번 깜박이기 전 단어를 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 256MB

 

입출력 예 :

입력	출력
4 acefdb	abcdef
1000 aaaaaa	aaaaaa
11 srama	sarma

 

다른 사람의 풀이 : 

스스로 풀어보던 풀이법이 시간초과를 겪고, 반복되는 사이클을 찾게되어 Set을 사용해 해결해보려 했으나 잘 풀리지 않아서 다른 사람의 풀이를 참고하게 되었다.

 

https://colabear754.tistory.com/156

[Kotlin] 백준 9519 : 졸려

 

주기를 알아내는 것 까진 동일했으나, 실제로 코드로 풀어나갈때 반복문을 통해 이전 단어를 만들어 가는 과정이 크게 달랐었다.

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    val x = readLine().toInt()
    val input = readLine()
    val backIndex = input.lastIndex - if (input.length % 2 == 1) 1 else 0
    val word = mutableSetOf<String>().apply { add(input) }

    while (true) {
        val cur = word.last()
        val sb = StringBuilder()

        for (i in cur.indices step 2) sb.append(cur[i])
        for (i in backIndex downTo 0 step 2) sb.append(cur[i])
        if (!word.add(sb.toString())) break
    }

    bw.write(word.toList()[x % word.size])
    bw.flush()
    bw.close()
}