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

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

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

 

나의 풀이

function solution(number, k) {
    const numArray = [...number];
    const stack = [];
    
    while (numArray.length) {
        if (k > 0 && stack[stack.length - 1] < numArray[0]) {
            stack.pop();
            k -= 1;
            continue;
        }
        
        stack.push(numArray.shift());
    }
    
    return stack.slice(0, stack.length - k).join("");
}

하지만 테스트 코드 10번을 계속 실패하였다.

 

결국 방법을 찾지 못하였고 검색으로 다른 분들의 코드를 살펴보았다.

차이점은 나처럼 숫자 문자열을 배열로 바꾸는 과정과 매 순간 push(shift)를 하지 않는 것이었다.

 

그래서 다음과 같이 변경하였다.

function solution(number, k) {
    const stack = [];
    let num = 0;
    let count = 0;
    
    while (true) {
        num = number[count];
        
        if (k > 0 && stack[stack.length - 1] < num) {
            stack.pop();
            k -= 1;
            continue;
        }
        
        stack.push(num);
        
        if (count === number.length - 1) break;
        
        count += 1;
    }
    
    return stack.slice(0, stack.length - k).join("");
}

pop과 push 메서드만을 사용하였다.

코드가 좀 길어졌지만 반복문에서 메서드 사용을 줄이니 속도면에서 큰 차이를 보였다.

 

수정 전 코드 테스트 결과

수정 후 코드 테스트 결과

특히 7번 8번은 속도가 10배는 빨라진 것 같다..

앞으로 한 줄 코드 등 짧은 코드를 추구하기보다, 시간 복잡도를 줄일 수 있는 코드를 작성하도록 많은 고민을 해보아야겠다.