프로그래머스 LV2 큰 수 만들기

문제

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

프로그래머스

 

해설

function solution(number, k) {
    let stack = [];

    let arr = number.split('').reverse();
     //1924 ->> 4291 
    while(arr.length && k>0){
        stack.push(arr.pop())  //4 3 2 3
        while(stack[stack.length-1] < arr[arr.length-1] && k>0) {
            stack.pop();
            k = k-1;
        }
    }

    if(k !== 0) stack = stack.slice(0, -k) 

    return stack.join('') + arr.reverse().join('')
}

처음 이 문제를 봤을 때 백트래킹 혹은 순열을 활용해서 구할려고 했으나 O(n**2)의 시간이 걸려 시간초과가 계속 났다.

스택을 활용해서 반대로 배열을 돌린다음 그 배열이 하향 곡선일 때는 계속 스택에 넣고 번쩍 상향 곡선이 그려진다면 스택에 맨 끝을 버리게 한다