programmers - 탐욕법 - 큰 수 만들기

문제 설명

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

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

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

제한 조건

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

---

문자열로 형태로 주어진 숫자들의 순서를 깨지 않으면서 최댓값을 구하는 문제.

function solution(number,k){
    let answer;
    let numberToArray = number.split('');
    let a = 0;
    let b = a + 1;
    
    while( numberToArray.length !== number.length - k ){
    
        if(numberToArray[a] > numberToArray[b] ){
            numberToArray.splice( numberToArray.indexOf(numberToArray[b]) ,1); 
            
            a += 1;
            b = a + 1;
        }else if( numberToArray[a] === numberToArray[b] ) {
            a = a + 2;
            b = a + 1;
            
        }else{
            numberToArray.splice( numberToArray.indexOf(numberToArray[a]) ,1);
        }
        
        
    }
    
    answer = numberToArray.join('');
    return answer;
}

좀 더 발전된 답안은 아래와 같다.

function solution(number, k) {
    let StNum = String(number);
    let num_length = StNum.length;
    let stack = [];
    let count = 0;
    
    for(let i = 0; i < num_length; i++){
        let element = number[i];
        if(stack.length === 0){
           stack.push(element);
           continue;
        }
        
        while(stack[stack.length-1] < element){
            stack.pop();
            count++;
            
            if(count === k) {
                return stack.join("") + number.substring(i, num_length);
            }
            
            if(stack.length === 0 ){
                break;
            }
            
        }
        
        stack.push(element);
        
    }
    
    return stack.join("").substring(0, num_length-k);
}

number는 "1924"처럼 문자열 안에 숫자가 붙어 있는 상황이다.
하나의 간편한 팁을 알게 되었다.
String(숫자를 감싼 따옴표 문자열) => typeof는 문자열로 유지되면서
마치 배열 [1, 9, 2, 4]처럼 인덱스를 이용해서 편하게 연산할 수 있다.
이 문제의 경우 let StNum = String(number)처럼 쓸 수 있다.

def solution(number, k):
    arr = []

    for i, num in enumerate(number):
        while len(arr) > 0 and arr[-1] < num and k > 0:
            arr.pop()
            k -= 1
        if k == 0:
            arr += list(number[i:])
            break
        arr.append(num)
        
    arr = arr[:-k] if k > 0 else arr
    answer = ''.join(arr)
    return answer

출처: https://dreammarker.tistory.com/92?category=697329
https://scarletbreeze.github.io/articles/2019-07/pythonKit문제풀이(4)탐욕법큰수