탐욕법(Greedy) / 2 / 큰 수 만들기

문제 설명

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

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

이 중 가장 큰 숫자는 94 입니다.

 

문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다.

number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를

문자열 형태로 return 하도록 solution 함수를 완성하세요.

 

제한 사항

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

 

문제 풀이 방법

• 앞의 수부터 차례로 배열에 넣는다.
• 첫 번째 수는 그냥 들어가고, 두 번째 수부터 앞의 수와 비교하여 넣어준다 (성공하면 k는 한개 줄여준다)
• 마지막에는 join('')을 해준다음 slice(0, number.length - k)를 해주었다.
  이는, number = "3333", k=1 같은 상황에서 사용할 수 있게 설정한 것이다.

 

주의 사항

1. number는 2자리 이상, 1,000,000자리 이하인 숫자 이기에 조합을 사용하게 된다면 런타임 에러가 난다.....
   3시간동안 조합으로 푼 거는 비밀.....

 

코드

function solution(number, k) {
    let arr = [];
    
    for(let i=0; i<number.length; i++){
        while(k > 0 && arr[arr.length - 1] < number[i]){
            arr.pop(number[i]);
            k -= 1;
        }
        arr.push(number[i]);
    }
    return arr.join('').slice(0, number.length - k);
}

 

못 푼 문제

function solution(number, k) {
    let answer = '';
    let arr = [...number];
    
    const getAnswer = () => {
        let numArr = getCombination(arr, number.length - k);
        let newArr = [];
        
        for(let i=0; i<numArr.length; i++){
            newArr.push(parseInt(numArr[i].join('')));
            newArr.sort((a, b) => b - a);
        }
        answer = String(newArr.shift());
    }
    
    //  조합을 구하는 함수
    const getCombination = (arr, num) => {
        const res = [];
        if(num === 1) return arr.map((v) => [v]);

        arr.forEach((v, idx, arr) => {
            const rest = arr.slice(idx+1);
            const combinations = getCombination(rest, num-1);
            const attach = combinations.map((combination) => [v, ...combination]);
            res.push(...attach);
        })
        return res;
    }
    getAnswer();
    return answer;
}