[Kotlin] 백준 2812번 - 크게 만들기

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

2812번: 크게 만들기

유형

그리디, 스택

풀이

포인트

 

• 필요한 만큼 삭제한다 -> 삭제했을 때 수의 길이는 항상 같다.
• 가장 크게 만든다 -> 앞에 나보다 작은 수가 있으면 삭제한다.

과정

 

1. 스택 선언
2. 입력 숫자를 앞에서 하나씩 확인 ->
   1. 필요한 만큼 다 삭제했다 -> 스택에 숫자 추가
   2. 삭제할 게 남아있다 ->
      1. 스택 위에 지금 숫자보다 큰 수가 있다 -> 삭제
      2. 위 과정을 스택이 비어있거나, 나보다 크거나 같은 수가 있거나, 삭제를 다 끝마칠 때까지 반복한다.
3. 수가 내림차순으로 잘 정렬돼 있으면, 위 과정에서 removeCount만큼 삭제가 일어나지 않을 수도 있으므로 남은 removeCount만큼 뒤에서 삭제한다.

Ex) 1253375에서 5개 삭제

- loop 0)

앞에 숫자가 없다. '1' 추가 (answer: 1)

- loop 1)

'1' < '2' => '1' 삭제, '2' 추가 (answer: 2)

- loop 2)

'2' < '5' =>  '2' 삭제, '5' 추가 (answer: 5)

- loop 3)

'5' > '3' =>  '3' 추가 (answer: 53)

- loop 4)

'3' == '3' =>  '3' 추가 (answer: 533)

- loop 5)

'3' < '7' =>  '3' 삭제 (answer: 53),

'3' < '7' => '3' 삭제, '7' 추가 (answer: 57)

- loop 6)

'7' > '5' => '5' 추가

- 예외 처리

삭제할 게 하나 남았으므로, 뒤에서 하나를 삭제한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var (_, removeCount) = readLine().split(" ").map(String::toInt)
    val strNumber = readLine()
    val answer = StringBuilder() // 스택으로 활용

    for (num in strNumber) {
        if (removeCount == 0) {
            answer.append(num)
            continue
        }

        // 감히 나보다 작은 녀석이 앞에 있어!? -> 삭제로 응징한다
        // 나보다 큰 행님 or 같은 애가 앞에 있다 -> ㅇㅋ 인정
        while (answer.isNotEmpty() && answer.last() < num && removeCount > 0) {
            answer.deleteAt(answer.lastIndex)
            removeCount--
        }
        answer.append(num)
    }

    // 숫자들이 이미 내림차순으로 잘 정렬돼있으면,
    // 남아있는 removeCount만큼 뒤에서부터 삭제한다
    while (removeCount-- > 0) {
        answer.deleteAt(answer.lastIndex)
    }
    print(answer)
}