🔎 큰 수 구하기

❓ 문제링크

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

📄 제출 코드

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

let number = "1924"
// let number = "09091"
let k = 2;
console.log(solution(number, k));

처음에 그냥 sort후에 뒤에꺼 두개를 뽑으면 되는거 아닌가? 라고 생각했다가 바로 테스트케이스 보고 생각을 고쳐먹었다. 테케를 보다보니 앞의 숫자가 뒤의 숫자보다 뒤에 나오면 안됐다.

풀이는 stack을 이용하였다.
처음 숫자를 뽑아 그 숫자가 stack의 가장 마지막 숫자보다 크면 뽑아내고, k를 1감소 시킨다.
그리고 그 숫자를 el에 넣는다.

ex)
1924의 경우
i=0 : 첫 요소를 push stack = [1], k=2 stack=[1]
i=1 : k>0 && stack[0] < 9 니까 1을 pop하고, 9를 push함. k=1 stack=[9]
i=2 : k>0 && stack[0] < 2 만족하지 않으니까, 그대로 push, k=1, stack=[9,2]
i=3 : k>0 && stack[1] < 4 만족하므로 2를 pop하고, 9를 push. k=0, stack=[9,4]

예외)
그냥 stack.join()을 하면 testCase12에서 error가 발생함.
stack.splice(stack.length - k, k);를 통해 12번 통과.
k가 0일 경우 스택은 그대로,
but k가 남아있으면 뒤에서부터 제거해준다. (ex. 1010,2 -> 11)

🎲 초기 코드

function solution(number, k) {
    
    let nums = number.split("");
    
    dfs(nums, (nums.length - k), 0, []);
    let temp = [];
    
    for (var i = 0; i < answers.length; i++) {
        temp.push((answers[i].toString()))
    }
    temp.sort();
    let answer = temp[temp.length - 1].replace(/,/gi, '');
    
    return answer;
}
let answers = [];
function dfs(nums, num, depth, arr) {
    if (depth == num) {
        answers.push([...arr])
    } else {
        for (var i = 0; i < nums.length; i++) {
            arr.push(nums[i]);
            dfs(nums.slice(i + 1), num, depth + 1, arr);
            arr.pop();
        }
    }
}

let number = "1924"
// let number = "09091"
let k = 2;
console.log(solution(number, k));

초기에 조합으로 number배열 중에 k자리수만큼 뽑는 조합을 가지고, sort하여 가장뒤에껄 뽑아냈다. 하지만 시간초과 발생으로 다른 방법을 찾다가 스택으로 해결하였다.

📘 참고

https://velog.io/@kimtaeeeny/프로그래머스-큰-수-만들기-javascript