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

문제

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

코딩테스트 연습 - 큰 수 만들기

어떤 숫자에서 k개 만큼의 숫자가 제거되었을 때 만들 수 있는 가장 큰 수를 구해야되는 문제이다. Greedy 알고리즘을 사용해 문제를 풀었고, 여기서 Greedy 알고리즘이란 매 순간 최선이라 판단되는 선택을 하면 가장 좋은 방법으로 문제를 해결할 수 있다라고 가정하는 아이디어에서 나온 것이다. 즉 미래는 생각하지 않고 당장 눈 앞에 닥친 문제만 생각하면 되는 것이다. 물론 이 방법으로 모든 문제가 풀리는 것은 아니지만 계산 시간이 적게 걸린다는 장점이 있기 때문에, Greedy 알고리즘으로 풀 수 있는 문제라면 이를 사용해 문제를 해결하는게 효율성측면에서 좋다. 

 

풀이 과정

function solution(num, k) {
    let answer = [];
    let i = 0;
    let rest = num.length - k;
    // 문자열로 주어진 숫자들을 내림차순 배열로 만든 뒤 중복 제거
    let number = [...new Set(num.split('').sort((a, b) => b - a))];
    // 남겨진 숫자가 있을 때 동안
    while(rest > 0){
        let delStart = (num.indexOf(number[i])) + 1;
        // '큰 숫자를 큰 단위에 적용하면 가장 큰 수를 만들 수 있다'라는 가정하에 진행
        // 큰 수부터 작은 수 순서대로 answer에 집어넣는다
        answer.push(number[i]);
        // (한 번 지나간 구간은 되돌아가지 못하기 때문에 아래와같은 조건이 필요하다)
        // num이 해당 숫자를 안 갖고 있으며
        // 추가해야될 숫자 개수 > 인덱스 i번째 뒤에 남은 숫자 개수라면
        if(!num.includes(number[i]) || num.slice(delStart).length < rest - 1){
            // answer에서 해당 숫자를 빼내고
            answer.pop();
            // i를 증가시킨다
            i++;
        // num이 해당 숫자를 갖고 있고
        // 추가해야될 숫자 개수 < 인덱스 i번째 뒤에 남은 숫자 개수라면
        }else{
            // num을 delStart부터 끝까지 잘라낸다(즉 i번째를 포함해 이전 범위는 삭제)
            num = num.slice(delStart);
            // 추가해야 될 숫자 개수를 감소시킨다
            rest--;
            // i는 0으로 초기화
            i = 0; 
        }
    }
    return answer.join('');
}

 

테스트케이스