백준 1464번 뒤집기 3 Kotlin

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

문제

---

생각하기

---

• 문자열

동작

처음에는 진짜 문제처럼 문자열을 뒤집어가면서 답을 찾도록 구현해야 하나 생각했는데, 해답을 찾지 못해 정답을 찾아보았다.

해결방법은 문자열을 Character 단위로 하나씩 분리해서 앞에 붙인 문자열과 뒤에 붙인 문자열 중 어떤게 사전순으로 빠른지 확인하고 지속적으로 사전순으로 빠른 문자열을 선택하면 정답을 찾을 수 있었다.

그래서 그리디 알고리즘이라는 것을 파악했다.

또한, Deque을 써서도 풀수있는 문제고 문자를 연결하면 되므로 StringBuilder를 통해서도 풀 수 있었다.

결과

코드

---

덱 사용

import java.io.*

// input
private var br = System.`in`.bufferedReader()

fun main() {
    val bw = System.out.bufferedWriter()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val S = br.readLine()
    val deque = ArrayDeque<Char>()
    deque.addLast(S[0])

    val len = S.length
    for (i in 1 until len) {
        val cur = S[i]

        if (cur <= deque.first()) {
            deque.addFirst(cur)
        } else {
            deque.addLast(cur)
        }
    }

    deque.forEach {
        sb.append(it)
    }

    return sb.toString()
} // End of solve()

StringBuilder 사용

import java.io.*

// input
private var br = System.`in`.bufferedReader()

fun main() {
    val bw = System.out.bufferedWriter()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val S = br.readLine()
    val n = S.length

    if (n == 0) {
        sb.append("")
        return sb.toString()
    } else if (n == 1) {
        sb.append(S)
        return sb.toString()
    }

    val result = StringBuilder()
    result.append(S[0])

    for (i in 1 until n) {
        val cur = S[i]
        val option1Str = cur + result.toString()
        val option2Str = result.toString() + cur

        if (option1Str < option2Str) {
            result.insert(0, cur)
        } else {
            result.append(cur)
        }
    }

    sb.append(result.toString())
    return sb.toString()
} // End of solve()