[프로그래머스] 큰 수 만들기 (Javascript)

문제

[프로그래머스] 큰 수 만들기

문제 정의

최대 길이 1,000,000자리의 숫자 문자열이 주어지고, 문자열에서 숫자를 k개 제거 했을 때 최댓값을 출력하는 문제다.

해결방안

풀이 1 (시간초과)

처음엔 제한 조건을 잘못 보고 number가 최대 1,000,000인줄 알았다.
그래서 최대 자릿수는 6이기 때문에 완전 탐색으로 풀 수 있을 줄 알았다.

function solution(number, k) {   
    let answer = 0;
    combination(0,'');
    function combination(cur,num){
        if(num.length === number.length - k){
            answer = Math.max(answer, +num);
            return;
        }
        for(let i=cur; i<number.length; i++){
            combination(i+1,num+number[i]);
        }
    }
    return answer.toString();
}

왜 시간초과가 나지? 하면서 제한 조건을 다시 보니 number의 "자릿수"가 최대 1,000,000이었다.
당연히 시간초과가 날 수 밖에 없었다...ㅎ

풀이 2

풀이 방법이 떠오르지 않아 다른 분의 풀이를 참고했다.

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

answer 배열에 숫자를 추가한 뒤, answer배열의 마지막 원소와 현재 number[i]를 비교한다.
만약 number[i]가 더 크다면 answer의 마지막 원소를 pop한다. 이는 숫자를 하나 빼는 것을 의미하므로 k도 1 감소시킨다.

만약 k가 0이 되어서 더이상 숫자를 뺄 수 없을 때는 이 작업을 수행할 수 없으므로 while문의 조건에 k > 0을 설정해준다.
그리고 answer 배열에 원소가 하나도 없을 경우에도 마찬가지로 숫자를 뺄 수 없기 때문에 answer.length > 0 조건도 걸어준다.

이렇게 하면 자릿수가 큰 위치에 큰 수가 오게된다.

만약 모든 반복문을 수행했는데, k가 남는 경우도 있을 수 있다.
예를 들면 "9876" 이라는 입력이 주어졌을 때, 반복문이 종료되면 answer = ["9","8","7","6"], k=2가 된다. 따라서 이런 경우에는 splice를 이용해서 마지막 원소부터 k자리만큼 제거해준다.

여기서 알아둬야 할 점은 answer[answer.length-1] < number[i]에서 문자열을 숫자로 변환하지 않고 그대로 대소관계를 비교한다는 점이다.
숫자 문자를 한 문자끼리 대소관계 비교할 때는 숫자로 형변환 해주지 않아도 큰 숫자가 ASCII코드상 더 큰 값을 가지기 때문에 올바른 값이 나오지만 여러 숫자 문자가 여러개일 경우 맨 앞 문자에 의해 대소 관계가 결정되므로 올바르지 않은 값이 나올 수 있다.
"3" > "1" // true
"3" > "10" // true
지금 문제에서는 문자 하나씩만 비교하는 상황이기 때문에 숫자로 변환하지 않아도 대소관계 비교가 가능하다.