[Kotlin] 백준 2812 : 크게 만들기

문제 링크

2812번: 크게 만들기

---

문제 해설

N자리 수에서 K개의 숫자를 지워서 만든 가장 큰 수라는 것은 결국 앞자리 숫자가 뒷자리 숫자보다 커야한다는 것을 의미한다. 이를 처리하기 위해 스택을 사용할 수 있다.

 

입력으로 주어진 수를 각 자리수의 배열로 생각하여 진행한다. 앞에서부터 각 자리의 숫자를 스택에 삽입한다. 이 때, 스택에 숫자를 삽입하기 전에 이미 삽입된 숫자들을 순차적으로 확인하여 현재 삽입해야 할 숫자보다 작은 숫자를 모두 제거하고, 제거한 숫자의 개수를 기록한다. 제거한 숫자의 개수가 K개가 되었다면 남은 모든 숫자를 스택에 삽입한다.

 

모든 자리의 숫자를 순회했는데 스택에서 제거된 숫자의 개수가 K개 미만인 경우가 생길 수 있다. 예를 들어, 54321의 경우에는 각 자리의 앞자리 숫자들이 모두 현재 자리의 숫자보다 크기 때문에 입력으로 주어진 수의 자리수를 순회하는 동안 제거되는 숫자가 없다. 이런 식으로 순회하는 동안 제거된 숫자의 개수가 K개보다 적을 경우에는 뒷자리의 숫자가 가장 작은 경우이므로 남은 개수만큼 스택에서 제거하면 된다.

 

결과를 출력할 땐 스택의 특성 상 뒤집어서 출력해야 한다.

Code

import java.util.LinkedList

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(' ').map { it.toInt() }
    val number = readLine()
    val stack = LinkedList<Char>()
    var count = 0
    for (num in number.indices) {
        if (count == k) {
            for (c in number.substring(num)) stack.push(c)
            break
        }
        while (stack.isNotEmpty() && stack.peek() < number[num] && count < k) {
            stack.pop()
            count++
        }
        stack.push(number[num])
    }
    while (count < k) {
        stack.pop()
        count++
    }
    println(stack.joinToString("").reversed())
}