백준 2812 크게 만들기 Kotlin (스택)

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

2812번: 크게 만들기

문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 스택

풀이

간단하게 작은 수부터 k개 제거한다면 3번 예제에 걸린다.

3번 예제를 보면 앞에서부터 작은 수를 제거해야 한다는 것을 알 수 있다. 그렇지만 작은 수의 기준이 애매해지는데 어떻게 해결할 수 있을까?

스택을 이용할 수 있다.

우선 앞에서부터 숫자를 하나씩 스택에 넣어준다.

만약 스택에 있는 값보다 큰 값이 있다면 스택에 있는 바깥의 값보다 작은 값들을 모두 제거해 준다.

예제 3번으로 예를 들면,

스택은 

- 4

- 4 1

- 7 //여기에 7이 들어오면서 앞에 작은 값들을 모두 제거해 준다. 

- 7 7

- 7 7 2

- 7 7 2 //여기에 5가 들어오면서 앞에 작은 값들을 모두 제거해 준다.

- 7 7 5 2

- 7 7 5 8 //여기에 8이 들어오면서 앞에 작은 값들을 모두 제거해 준다.

- 7 7 5 8 4

- 7 7 5 8 4 1

이제 이 값들을 순서대로 출력하기만 하면 된다.

 

위의 경우에는 k=4이고, 4개만큼 모두 삭제했다.

아래의 경우를 보자.

4 2

1110

4개 중 2개를 삭제해야 하는데 위의 로직대로라면

- 1

- 1 1

- 1 1 1

- 1 1 1 0

스택에 삭제되는 것은 없고 모두 삽입만 된다.

이런 경우를 방지하기 위해 위의 로직이 끝나면 

아직 삭제되지 않은 수만큼 스택의 위에서부터 삭제해 주어야 한다.

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    //input
    val (n, k) = getIntList()
    val input = br.readLine()
    val stk = Stack<Int>()
    var idx = 0
    var cnt = 0
    var sb = StringBuilder()
    for (i in input.indices) {
        val num = Character.getNumericValue(input.get(i))
        if (stk.isEmpty()) {
            stk.add(num)
        } else {
            while (cnt < k && stk.isNotEmpty() && stk.peek() < num) {
                stk.pop()
                cnt++
            }
            stk.add(num)
        }
    }
    //남은 작은 수 제거
    while(cnt < k && stk.isNotEmpty()){
        stk.pop()
        cnt++
    }
    for (num in stk) {
        sb.append(num.toString())
    }
    write("${sb}")
    close()
}