[알고리즘 / Kotlin] 프로그래머스 - 큰 수 만들기

큰 수 만들기

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.

예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24]를 만들 수 있습니다. 이 중 가장 큰 숫자는 94입니다.

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

 

입출력 예

내 풀이

처음에는 단순히 앞부분부터 최댓값을 찾고 answer += max 를 하고 그다음 인덱스부터 substring하는 방식을 반복하며 풀었지만 테스트 케이스 9, 10번에서 시간 초과로 인해 다른 방법으로 풀어야겠다고 생각했습니다.

 

그래서 생각했던 것이 stack을 통해서 기본적으로 문자열의 문자 하나하나를 push하면서 만약 새로 넣을 숫자 문자가 이전 숫자 문자보다 크면 count(처음에 k로 초기화)를 하나 줄이고 해당 문자를 꺼냅니다. 이때 count가 0이면 더 이상 꺼내지 않고 계속 넣어줍니다.

 

• stack에 각 문자들을 push 해준다. (이 때 이전 문자보다 새로 삽입할 문자가 크면 이전 문자를 pop해주고 count를 하나 감소시킨다.)
• 최종적으로 남은 count 수만큼 pop 해준다.

 

for(i in 1..count) stack.pop()의 케이스는 number가 "98765" 같은 경우인데 count는 k 그대로 이기 때문에 k 만큼 뒤에서부터 문자를 제거해주어야 합니다. 이는 stack이 LIFO구조이기에 가능합니다.

 

📝 코드

import java.util.*

class Solution {
    fun solution(number: String, k: Int): String {
        var answer = ""
        var count = k
     	val stack = Stack<Char>()

    number.forEach {
        while(stack.isNotEmpty() && stack.peek() < it && count >0){
            stack.pop()
            count--;
        }
        stack.push(it)
    }

    	for(i in 1..count) stack.pop()

        return  stack.toArray().joinToString("")
    }
}

 

다른 사람의 풀이

예제 1

class Solution {
    fun solution(number: String, k: Int): String {
        val answerBuilder = StringBuilder()
        with(number.toCharArray()) {
            var remainLetterCount = number.length - k
            var left = 0
            while(remainLetterCount != 0) {
                if(remainLetterCount == size - left) {
                    for(eachIndex in left .. size - 1) answerBuilder.append(this[eachIndex])
                    return answerBuilder.toString()
                }
                var frontSubMaxValue = '/'
                var frontSubMaxIndex = -1
                for(eachIndex in left .. size - remainLetterCount) {
                    if(frontSubMaxValue < this[eachIndex]) {
                        frontSubMaxValue = this[eachIndex]
                        frontSubMaxIndex = eachIndex
                    }
                }
                answerBuilder.append(frontSubMaxValue)
                remainLetterCount--
                left = frontSubMaxIndex + 1
            }
        }
        return answerBuilder.toString()
    }
}

위와 같은 경우는 StringBuilder를 통해 문제를 해결하였습니다.

 

기존의 String 객체의 경우 한 번 생성되면 할당된 공간이 변하지 않고 StringBuilder의 경우 객체의 공간이 부족해지면 버퍼의 크기를 유연하게 늘려줍니다.

 

String의 경우 +연산을 사용하면 String의 객체 수가 늘어나기 때문에 프로그램의 성능이 느려집니다. 그래서 문자열을 변경하는 작업이 많을 경우 StringBuilder를 사용하는 것을 권장하고 있습니다. 아마 저 같은 경우 기존에 String 객체를 가지고 문제를 해결하면서 + 연산이 기하급수적으로 많아져 시간 초과가 발생했던 것 같습니다.

 

배운 점

문제를 이해하는 데는 오래 걸리지 않았지만 막상 다 풀고 나니 효율성에서 막혀서 머리가 하얘졌던 것 같습니다. 지금 다시 생각해보면 그리 어려운 부분은 아니었는데 당황하니 풀 수 있던 문제도 잘 못 풀었던 것 같습니다. 앞으로는 한 문제를 풀어도 다양한 방식으로 풀어보는 힘을 키워야 할 것 같습니다.