큰 수 만들기 make big numbers

💡

Level 2 210923 https://programmers.co.kr/learn/courses/30/lessons/42883

문제 설명

어떤 숫자에서 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

return

"1924"

"94"

"1231234"

"3234"

"4177252841"

"775841"

My solution

주어진 number는 순서를 바꿀 수가 없다. 처음에 문제를 잘 이해 안되는 것은 이것 때문일 것이다. k개만큼 뽑고 "순서를 유지한 채로 만들어진 최댓값"을 return해야 한다.

입출력 예 1을 보면 1924이고 k가 2이다. number에서 k개 뽑으면 리턴값은 2자리 수가 된다.

체크 배열을 이용해서 선택한 인덱스 이전 인덱스까지 전부 체크해주는 방식으로 k개의 숫자를 뽑은 조합 중에서 숫자의 순서를 유지한 조합만 남길 수 있었다. 재귀의 깊이는 tmp가 number.length - k 개면 종료되도록 했고 주어진 세 개의 테스트케이스는 다 통과했다.

function solution(number, k) {
    let answer = [];
    let n = number.length

    let ch = Array.from({ length: n }, () => 0);
    let tmp = Array.from({ length: n-k }, () => 0);
    function DFS(L) {
        if (L === n-k) {
            answer.push(tmp.slice().join(''));
        } else {
            for (let i = 0; i < n; i++) {
                if (ch[i] === 0) {
                    for(let j=0; j <= i; j++){
                        ch[j] = 1; // 이 인덱스의 이전 인덱스들까지 차단
                    }
                    tmp[L] = number[i];
                    DFS(L + 1);
                    for(let j=0; j <= i; j++){
                        ch[j] = 0; // 이 인덱스의 이전 인덱스들까지 해제
                    }
                }
            }
        }
    }
    DFS(0);
    let max = Number.MIN_SAFE_INTEGER;
    for(let x of answer ){
         max = Math.max(max, Number(x))
    }
    
    return max.toString();
}

헌데 정확도가 처참하다.

프로그래머스 런타임 에러를 검색해보니

6. 재귀 호출이 너무 깊어질 경우 3번과 비슷한 케이스인데 재귀 호출의 횟수가 스택 크기 제한을 넘어가는 경우 런타임 에러가 발생합니다. 출처:https://jaimemin.tistory.com/1522 [꾸준함]

아마도 재귀를 사용한 것도 그렇고 모든 값을 하나씩 탐색해서 범위조절이 필요할 것 같다. 범위를 어떻게 조절해줘야할지 생각해보니 최댓값이 되는 숫자를 뽑을 수 있는 자리가 k에 따라 달라진다는 걸 알 수 있었다.

체크배열에 넣어서 조건을 주었듯이 최댓값이 되는 숫자를 하나 뽑고 나면 그 다음 뽑을 숫자는 그 숫자의 다음의 인덱스부터 마지막 인덱스까지의 범위 내에서만 뽑을 수 있다.

유의해야할 것은 아무것도 뽑지 않았을 때 0번 인덱스 ~ n - k번 인덱스까지 확인한다는 것이고 이후 max 값이 찾아질 때마다 그 인덱스로 cur(커서)를 업데이트해준다. 이 cur 값을 처리하는 것이 중요하다. cur을 0으로 선언하여 j에 할당한 뒤 n-k번 인덱스까지 탐색하게 되면 그 다음 max 값을 만난 뒤 cur을 +1해서 업데이트해준다면 다음은 cur+1 인덱스부터 탐색해나갈 것이다. 그렇게 정해진 max값을 가지고 다음 루프로 가면 cur(선택된 max값의 인덱스)의 다음 값부터 max를 구해나갈 것이다.

위와 같이 구현해서 제출해보니 테스트케이스 10번이 시간초과가 났다.

반복문의 횟수를 많이 줄인 것 같은데 잘 모르겠어서 찾아보니까 number[j]가 9가 나오면 max를 찾기 위한 탐색을 더이상 하지 않게 해야된단다. 이 코드는 c나 c++같은 언어는 걸리지 않아서 추가적으로 시간을 단축하는 용도로 쓰라고 하던데 js는 여러모로 남다르다.

결국 아래의 코드로 통과했다.

소스 코드

function solution(number, k) {
    let answer = "";
    let cur = 0;

    for (let i = number.length - k; i > 0; i--) {
        let max = "0";
        // console.log("i", i, cur);

        for (let j = cur; j <= number.length - i; j++) {
            // console.log("j", j, number[j]);

            if (max < number[j]) {
                max = number[j];
                cur = j + 1;