Programmers - Greedy [큰 수 만들기]

1. 문제

문제 설명

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

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

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

제한 조건

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

입출력 예

number                                         k                                                 return

1924	2	94
1231234	3	3234
4177252841	4	775841

2. 내풀이

function solution(numbers, k) {
    let number = numbers.split("").map(Number);
    let arr = [];
    // 맨 앞에서 시작한다.
    for (let i = 0; i < number.length; i++) {
        let current = number[i];

        // 만약 현재 숫자가 arr의 마지막 숫자보다 크다면 arr의 마지막 숫자를 제거
        // 현재 숫자가 가장 크다면 arr은 모두 제거되어야 한다.
        while(true){
            // 제거할 숫자들이 모두 제거되면 break;
            if(k <= 0){
                break;
            }
            // arr의 마지막 숫자가 현재 숫자보다 작을경우 arr마지막 숫자 제거
            if(arr[arr.length - 1] < current){
                arr.pop();
                k--;
            }else{
                break;
            }
        }
        
        // arr은 무조건 추가
        arr.push(current);
    }

    // k개 만큼 모두 제거하지 못한 경우도 있다.
    // arr을 뒤에서 k개 만큼 제거한다.
    arr.splice(arr.length - k, k)
    console.log(arr);
    let answer = arr.join('');
    return answer;
}

let number = "4177252841";
let k = 4;

console.log(solution(number, k));

- 이문제는 절대 combination 문제가 아니다. number가 100만 자리면 애초에 재귀함수든 뭐든 숫자 조합의 수가 너무크다.

- 숫자를 제거해 나가며 추가해야하는 문제이다.

- 처음에는 맨뒤에서 부터 이전숫자보다 작은 숫자를 제거하며 늘려나갔지만 끝에서 부터 늘려나가면 maximum 배열밖에 안된다.

- 어차피 가장큰수가 되려면 앞에서 부터 큰숫자를 받아야만하고 k개의 숫자를 제거하면 더이상 제거할 숫자가 없으므로 바로 답이 나온다.

3. 다른 사람 풀이

- 맨 뒤에서 부터 이전숫자 보다 작은 숫자를 제거하며 늘려나가다가 틀렸다. 해서 다른사람의 풀이를 참고했다.

4. Tip

- 형변환 할때는 숫자로 Number(variable) 이렇게 한다.

- map함수는 파이썬과 비슷하다. String.map(함수)

- node js 는 js를 러닝하는 환경이라서 js도 러닝할수 있나보다. 그냥 node js는 그냥 js 아닌가?