[프로그래머스][Kotlin] 큰 수 만들기

해당 문제는 작성하는 사람에 따라 조금 다르겠지만 저의 경우는 데크와 카운터를 이용하여 작성하였습니다.

 

처음에 해당 문제를 보고나서 반복문은 1번만 사용하는 코드로 작성을 해야 시간복잡도에서 문제 없이 진행 될 수 있음을 알았기에 처음에 작성하는 것에 있어서는 문제가 없었습니다.

 

그런데 낮은수를 제거할때 자릿수 계산에서 식이 딱 떠오르지 않아 손으로 그려보면서 자체디버깅을 하고 있었는데 생각해보니 큰 수를 만들려면 뒤에 큰수가 얼마나 있던 앞에 작은 수가 없어야 된다는 규칙과 앞에서 작은수를 제거하면서 k 만큰 제거 한다면 해당 수가 가장 큰 수임을 확인할 수 있었습니다. 

해당 방식으로 코드를 작성하여 통과 하였습니다.

 

하기는 제가 작성한 코드와 실행결과 입니다.

import java.util.ArrayDeque

class Solution {
    fun solution(number: String, k: Int): String {
        var answer = StringBuilder()
        var dq = ArrayDeque<Int>()
        
        var count = 0
        
        for(i in 0 .. number.length-1){

            // 저장된 수가 없다면 수 저장
            if(dq.isEmpty() ){
                dq.add(number[i].toString().toInt())
                continue
            }

            // 낮은 수 제거
            while(!dq.isEmpty()){
                if(dq.peekLast() < number[i].toString().toInt() && count < k){
                    dq.pollLast()
                    count++
                } else {
                    break
                }
            }
            dq.addLast(number[i].toString().toInt())

        }
        
        repeat(number.length-k){
            answer.append(dq.pollFirst())
        }

        return answer.toString()
    }
}

테스트 1 〉	통과 (0.09ms, 61.1MB)
테스트 2 〉	통과 (0.21ms, 58.5MB)
테스트 3 〉	통과 (0.41ms, 58.6MB)
테스트 4 〉	통과 (1.66ms, 59.9MB)
테스트 5 〉	통과 (2.78ms, 57.8MB)
테스트 6 〉	통과 (8.92ms, 61.7MB)
테스트 7 〉	통과 (35.41ms, 65.6MB)
테스트 8 〉	통과 (54.73ms, 73MB)
테스트 9 〉	통과 (68.86ms, 80.8MB)
테스트 10 〉	통과 (111.55ms, 89.5MB)
테스트 11 〉	통과 (0.06ms, 61.1MB)
테스트 12 〉	통과 (0.10ms, 59.6MB)