큰 수 만들기

Problem

어떤 숫자에서 k개의 수를 제거했을 때 만들 수 있는 가장 큰 수를 문자열로 반환하는 함수 구현

Algorithm

Greedy : 탐욕법이라고 불리며, 최적해를 구하는데 사용되는 근사적인 방법이다. 여러 경우 중 하나를 결정할 때마다 매 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종 해답에 도달

Solution

1. stack이라는 변수명을 가진 빈 배열 선언 (매 순간 최적의 값을 담는 공간)
2. number 문자열을 순회하여 현재의 숫자를 stack에 담기
3. number 문자열 순회 중, 뺄 수(k개의 수)가 남았고 현재의 수가 stack의 top보다 크다면 현재의 수보다 stack의 top이 커지거나 stack이 빌 때까지 stack에서 빼기
4. number 문자열 순회가 끝나고도 뺄 수(k개의 수)가 남았으면, stack의 top 제거
5. stack을 문자열로 변환하여 반환

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