[JS] 프로그래머스 / 탐욕법(Greedy) / 큰 수 만들기

문제

프로그래머스

핵심 아이디어

• 탐욕법(Greedy Algorithm)은 문제를 해결할 때 각 단계에서 그 순간에 최선이라고 생각되는 선택을 하는 방법이다. 매 선택이 문제 전체의 최적해로 이어진다고 가정하고 진행하는 방식이다.
• 스택을 이용해 주어진 숫자를 앞자리에서부터 하나씩 비교해가며 큰 것만 남긴다.
• 정답 자리수까지 해당 작업을 반복하고 남은 숫자를 문자열로 바꾼다.
• 스택에서 필요한 숫자만 남겨 최종적으로 k개만큼 제거된 결과를 반환한다.

정답

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

  for (const num of number) {
    while (k > 0 && num > stack[stack.length - 1]) {
      stack.pop();
      k--;
    }

    stack.push(num);
  }

  return stack.join("").slice(0, number.length - k);
}