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

출처: unsplash.com

 

크게 만들기(2812번)

Gold 3

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

 

문제 내용

 

문제 접근

n자리의 숫자가 주어지고, 숫자에서 k개의 숫자를 뺀 숫자의 경우들 중, 가장 큰 값을 출력해야 한다.

가장 큰 값을 얻기 위해서는 맨 앞자리의 수가 제일 크고, 마지막 자릿수가 제일 작은 내림차순의 숫자에 가까워져야 제일 커진다.

stack에 값을 넣으면서 들어간 값보다 더 큰 수가 들어오면 stack에 들어간 숫자를 빼는 방식으로 stack을 사용해야 한다.

k번 숫자를 지우고 나면 나머지 숫자들은 그대로 stack에 넣어서 출력해 주면 된다.

 

 

문제 해결 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.Stack

private val stack = Stack<Int>()

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (addCnt, removeCnt) = readLine().split(" ").map { it.toInt() }
    val number = readLine().map { it.digitToInt() }

    var toRemoveCnt = 0
    for (i in number.indices) {
        while (stack.isNotEmpty() && toRemoveCnt != removeCnt && stack.peek() < number[i]) {
            stack.pop()
            toRemoveCnt++
        }

        if (stack.size < addCnt - removeCnt) stack.add(number[i])
    }

    println(stack.joinToString(""))
}

 

문제 풀이

number에 입력받은 숫자를 list형태로 받아 준다.

삭제한 숫자의 개수를 셀 toRemoveCnt를 생성한다.

 

1. 일단 처음에는 stack이 비어 있기 때문에 첫 번째 숫자를 넣어 준다. 나중에는 stack의 size가 나와야 하는 결과 자릿수를 오버하지 않을 때만 값을 넣어 준다.

2. 두 번째 숫자부터는 들어오는 숫자가 stack에 가장 마지막에 들어간 값보다 크다면 반복해서 stack에서 지워 주고, 삭제 카운트를 늘린다.

이 2가지의 과정을 반복하다 보면 최종 결과가 나오게 된다.

 

예를 들어 설명해 보겠다.

4177252841의 숫자에서 4개의 숫자를 뺀 수들 중 가장 큰 값을 찾아 주어야 한다.

 

먼저 4부터 시작한다.

사진 1-1

사진 1-1) stack이 비어 있으므로 4는 프리패스로 stack에 들어가고, 다음 데이터인 1은 4보다 작은 값이기 때문에 들어갈 수 있다.

사진 1-2

사진 1-2) 4와 1이 들어간 다음에는 7의 차례이다.

stack에 마지막에 들어간 값인 1보다 7이 더 작기 때문에 stack에서 1을 pop으로 지운다.

다음 값인 4도 7보다 작기 때문에 stack에서 4를 pop으로 지운다. 그러면 총 지운 숫자의 개수는 2개가 된다.

빈 stack에 7을 넣어 준다.

사진 1-3

사진 1-3) 다음에 들어간 7은 stack에 들어간 마지막 값인 7과 값이 같기 때문에 stack에 넣는다.

다음 값인 2는 7보다 작기 때문에 stack에 들어갈 수 있다.

하지만 5의 차례가 되면 5보다 작은 2는 pop 되고, 7은 5보다 크기 때문에 pop 되지 않는다(지운 숫자의 개수는 3개).

사진 1-4

사진 1-4) 다음으로 들어간 2는 5보다 작기 때문에 stack에 들어올 수 있다.

다음 값인 8의 차례이다.

현재 stack에 마지막으로 들어간 2는 8보다 작기 때문에 2를 stack에서 지운다(지순 숫자의 개수는 4개).

다음 stack의 마지막으로 들어간 수인 5는 8보다 작지만 지순 숫자가 문제에서 원하는 4개가 모두 채워졌기 때문에 5는 pop 되지 않고, 8이 그대로 stack에 들어간다.

사진 1-5

사진 1-5) 8 다음으로 남은 숫자인 4, 1이 차례대로 stack에 들어가면서 결과는 다음과 같아진다.

이제 stack list 7, 7, 5, 8, 4, 1을 숫자로 바꿔서 출력하면 문제의 답인 775841과 일치하게 된다.

 

 

문제 해결 과정

처음에는 ArrayDeque를 이용해 순환하면서 현재 값과 다음 값을 비교해 다음 값이 현재 값보다 크다면 현재 값을 지우는 방식으로 구현하였지만 아래의 반례에서 막히게 되었다.

6 4
321123

output: 3213
answer: 3223

현재 값과 다음의 값을 비교하다 보니 최적의 값을 찾을 수 없어서 첫 번째 1이 남아 최적값보다 작은 값이 나오게 되었다.

카테고리가 stack이라서 stack에 데이터를 모두 넣고 문제를 풀 수 있는 방법을 생각해 봤지만 생각나는 게 없었다.

결국 풀이를 참고해서 문제를 해결하긴 했지만, stack에 값을 구함과 동시에 정답에 서서히 가까워지는 방식으로 구현이 되더라.

풀이를 보기 전까지는 stack을 2개를 만들어서 문제를 해결해야 하는 줄 알았다.

stack을 이렇게도 써먹을 수 있다는 사실을 알게 해 준 문제.