[JS] 큰 수 만들기

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

프로그래머스

나의 풀이

처음에는 slice를 통해 다음과 같이 접근하였다.

 

인접한 두 수의 크기를 비교하여
앞의 수가 뒤의 수보다 작으면 앞의 수를 제거하기
그렇게 다 제거 했는데에도 k개의 수를 제거하지 못했을 경우
뒤에서부터 남은 수 자르기 

 

코드는 다음과 같다

function solution(number, k) {
    let answer = number;
    let pointer = 0;
    
    while (k > 0) {
        if (answer[pointer + 1] === undefined) break;
        if (answer[pointer] < answer[pointer + 1]) {
            answer = answer.slice(0, pointer).concat(answer.slice(pointer + 1, answer.length));
            k--;
            pointer = Math.max(pointer - 1, 0);
        } else {
            pointer++;
        }
    }
    
    return answer.slice(0, answer.length - k);
}

 

하지만 테스트케이스에서 시간초과가 나서...

slice가 아닌 다른 방법으로 접근해야 한다고 한다.

 

그래서 이용한게 stack 방식이다

 

접근 방식을 설명하자면 

 

차례차례 stack에 숫자를 쌓지만,

stack의 숫자와 현재 가리키는 숫자를 비교하여

stack의 숫자가 작을경우 stack 숫자를 제거하는 방식

 

코드는 다음과 같다

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

 

결론

slice, splice, 이중 for문... 등등

시간복잡도가 늘어날 거 같은 경우, 다른 방법이 없는지 다시 생각해봐야겠다