[그리디 & 스택] 프로그래머스 '큰 수 만들기' - js

1. 문제

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

프로그래머스

2. 코드

처음 푼 코드)

10번 테케 런타임에러와 12번 테케 실패가 나왔다.

function solution(number, k) {
    let removed = 0;
    number = number.split("");
    let temp = number.slice();
    temp = temp.slice(0,k);
    let max = Math.max(...temp);
    let i = 0;
    
    while(removed < k && i < number.length){
        if(i===0 & number[i] < max){
            number.splice(i,1);
            removed++;
            i = 0;
        }else if(number[i] < number[i+1]){
           number.splice(i,1);
            removed++;
          i = 0;
        }else i++;
    }
    
    return number.join("");
}

+ 다시 보니 내가 짠 코드인데도 전혀 이해를 못하겠다 ㅋㅋㅋㅋㅋㅋㅋ이래서 틀렸구나;;

정답 코드)

처음 짠 코드의 개선법이 잘 떠오르지 않아 새로운 방법을 검색하다가 스택으로 푸는 방법을 찾았다.

https://school.programmers.co.kr/questions/45028

프로그래머스

순회를 할때 앞에 나온 것들을 저장해뒀다가 다시 활용해야 할 때 어려가지 자료구조를 이용할 수 있지만, 이럴 경우 stack만으로 높은 효율을 낼 수 있다고 한다. 

이 문제에서도 앞에 나온 것들을 삭제해나가는 것이 아니라 최대한 큰 수를 만들기 위해 앞에 것들을 저장해두어야 한다! 앞으로 이런 유형이 나오면 스택을 꼭 기억해야겠다.

주의할 점은 stack을 이용할 때, 원본 배열 arr 또한 stack으로 만들어야 한다는 것이라고 한다. 기존 순서대로 순회하여 앞에서부터 shift() 로 꺼낸다면, 결국 queue가 되어버려 시간 복잡도에 통과할 수 없다.

이건 또 다른 그리디 문제를 풀 때 직접 겪어보았던 것 같다. 스택을 이용할 때는 원본도 스택으로 만들기(shift보다는 pop 사용을 지양)!

function solution(number, k) {
    let stack = [];
    // 원본 배열도 스택으로 만들기
    let arr = number.split("").reverse();
    
    while(arr.length && k > 0){
        stack.push(arr.pop());
        while(stack[stack.length-1] < arr[arr.length-1] && k > 0){
            stack.pop();
            k--;
        }
    }
    // 원본 배열에서 다 스택으로 꺼냈는데도 k가 0 이상이라면 스택 뒤에서 자르기
    // 0번째부터 끝에서 k번째 요소까지 추출
    if(k > 0) stack = stack.slice(0,-k);
    
    return stack.join("") + arr.reverse().join("");
}

이 문제는 직접 손으로 과정을 써가며 이해하니 조금 더 빨리 이해되었다. 역시 알고리즘 풀 때 노트는 필수...

 

복기

4/11