[프로그래머스] Lv2. 큰 수 만들기 -JavaScript

문제분류 : 코팅테스트 연습

난이도 : Level 2

출처 : 프로그래머스 - 큰 수 만들기

문제

제한 조건

📌 내가 생각한 풀이

1. 처음 생각한 풀이

Q) 조합 알고리즘을 이용하여 모든 경우의 수를 찾고, 그 중 가장 큰 값을 뽑으면 어떨까?

A) 문제점 : 문제 취지에 맞지 않는다. number는 순서가 정해져있는 수이지만, 조합은 순서를 고려하지 않고 뽑는 경우의 수 이기 때문에 해당값을 만족할 수 없다.

2. 문제 해결 풀이

스택에 값을 넣어주고, 대소비교를 통하여, 스택에서 제거하자!

function solution(number, k) {
    var answer = '';
    var stack = [];
    for(var i =0; i<number.length; i++){
        var val = number[i];
        //while문을 통하여, 현재 stack에 있는 값들 줓 새로 push되는 값보다 작은 값들을 모두제거
        while(k > 0 && stack[stack.length-1] < val){
            stack.pop();
            k--;
        }
        stack.push(val);
    }
    return answer = stack.join('')
}

결과

테스트케이스 12번만 통과가 안됐다. 이유가 뭘까?

number = "4321", k=1 일때를 생각해보자!

위 코드로 종료시
for문 종료후 stack에는 [4,3,2,1]이 존재하고, k=1이다.
즉 k > 0일 경우에 처리를 따로 해주어야 하는데, stack.length-k부터 k개를 제거해주면 된다

function solution(number, k) {
    var answer = '';
    var stack = [];
    for(var i =0; i<number.length; i++){
        var val = number[i];
        //while문을 통하여, 현재 stack에 있는 값들 줓 새로 push되는 값보다 작은 값들을 모두제거
        while(k > 0 && stack[stack.length-1] < val){
            stack.pop();
            k--;
        }
        stack.push(val);
    }
    // k>0일 경우 stack.length-k인덱스부터, k개는 제거해주어야한다.
    stack.splice(stack.length-k, k);
    return answer = stack.join('')
}

결과

📌 느낀점

순서가 존재하지 않는 모든 경우의 수를 찾을 때는 조합을 사용하자
순서가 존재하는 모든 경우의 수를 찾을 때는 스택을 사용하자