[BOJ] 1467 수 지우기 - P2

TaeGN·2024년 9월 18일

algorithm kotlin

BOJ Platinum Challenge

목록 보기

86/114

문제풀이

세준이가 가지고 있는 문자열의 길이를 N이라 하고, 삭제할 문자열의 길이를 M이라 했을 때, (N - M)길이의 문자열을 만들면 된다.
현재 단계에서 가능한 가장 큰 수를 배치한다. -> 해당 숫자 앞에 있는 모든 숫자가 삭제 가능하고, 해당 숫자를 선택할 수 있어야 한다.
2번을 (N - M)번 반복한다.

주의사항

소요시간

1시간 40분

package 백준.Platinum.P2.p1467_수지우기

fun main() {
    fun result(S: String, P: String): String {
        val remainedCountArr = IntArray(10)
        val removeCountArr = IntArray(10)
        S.forEach { remainedCountArr[it - '0']++ }
        P.forEach { removeCountArr[it - '0']++; remainedCountArr[it - '0']-- }
        val sb = StringBuilder()
        var s = S
        val countArr = IntArray(10)
        repeat(S.length - P.length) {
            for (i in 9 downTo 0) {
                if (remainedCountArr[i] <= 0) continue
                val idx = s.indexOf('0' + i)
                if (idx == -1) continue
                countArr.fill(0)
                for (j in 0 until idx) {
                    countArr[s[j] - '0']++
                }
                if ((0..9).all { removeCountArr[it] >= countArr[it] }) {
                    for (j in 0 until 9) {
                        removeCountArr[j] -= countArr[j]
                    }
                    sb.append(i)
                    s = s.substring(idx + 1)
                    remainedCountArr[i]--
                    break
                }
            }
        }
        return sb.toString()
    }
    println(result(readln(), readln()))
}