큰 수 만들기

October 14, 2019 • ☕️ 3 min read
algorithm/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의 자릿수 미만인 자연수입니다.

입출력 예

number	k	return
1924	2	94
1231234	3	3234
4177252841	4	775841

출처

풀이

큰 수를 만들기 위해서는 수의 0번째 인덱스부터 k+1 인덱스까지 중에 가장 큰 수가 와야 한다는 말이다.

즉, number = “21305”이고 k = 2 일 때, “213” 중에서 가장 큰 수인 “3”을 찾았다면 3이 가장 앞에 오게 해야한다는 뜻이다.

시도 1

callstack 초과가 떴다. 심지어 Math.max 에서 떴다.

초과가 뜬 테스트 케이스는 10번.

예시 케이스는 number = “99999…99”로 9가 백만개이고 k = 999999.

Math.max 말고 다른 방법으로 Max를 찾는 시도를 했다.

 function solution(number, k) {
    let answer = '';

    number = number.split('').map(Number);

    while (k) {
        if (number.length === k) {
            break;
        }

        const maxValue = Math.max(...number.slice(0, k + 1));
        const maxIndex = number.indexOf(maxValue);

        if (maxIndex) {
            number.splice(0, maxIndex);
            k -= maxIndex;
        }

        answer += number.shift();

        if (!k && number.length) {
            answer += number.join('');
        }
    }

    return answer;
}

시도 2

콜 스택 초과는 아니지만 시간 초과가 떴다.

하긴 백만개의 수를 계속해서 loop를 돈다는 건 말이 안 된다.

function solution(number, k) {
    let answer = '';

    number = number.split('').map(Number);

    while (k) {
        if (number.length === k) {
            break;
        }

        let maxValue = -1, maxIndex = 0, n;

        for (let i = 0; i < k + 1; i++) {
            let n = number[i];
            if (maxValue < n) {
                maxValue = n;
                maxIndex = i;
            }
        }

        if (maxIndex) {
            number.splice(0, maxIndex);
            k -= maxIndex;
        }

        answer += number.shift();

        if (!k && number.length) {
            answer += number.join('');
        }
    }

    return answer;
}

시도 3

시도 1과 2는 k개의 수를 제거해나가는 작업이었다.

그러나 반대로 number.length - k를 찾아가는 작업으로도 생각할 수 있다.

이 경우도 조금 위태위태하지만 시간초과는 간신히 벗어날 수 있다.

function solution(number, k) {
    let answer = '';

    number = number.split('').map(Number);

    let resLen = number.length - k;

    let cursor = 0;
    while (resLen) {
        let max = -1, maxIndex = 0;

        for (let i = cursor; i <= number.length - resLen; i++) {
            if (max < number[i]) {
                max = number[i];
                maxIndex = i;
            }
        }

        cursor = maxIndex + 1;
        answer += max;

        resLen--;
    }

    return answer;
}

누군가의 해결법

내가 생각한 접근법과 동일하다. 그러나 그걸 풀어내는 방법이 다르다.

function solution(number, k) {
    var b = [];
    for (var i = 0; i < number.length; i++) {
        var c = number[i];
        while (k > 0 && b.length > 0 && b[b.length - 1] < c) {
            b.pop();
            k--;
        }
        b.push(c);
    }
    b.splice(b.length - k, k);
    var answer = b.join('');
    return answer;
}