[프로그래머스] 큰 수 만들기

문제:

https://programmers.co.kr/learn/courses/30/lessons/42883?language=javascript
카테고리 : 그리드

문제 접근 :

주어진 숫자에서 k개의 숫자를 제거했을때 만들 수 있는 모든 숫자 중 가장 큰 수를 구하는 문제이다.
처음 문제를 풀이할때, DFS로 조합방식으로 접근하였고 node.js에서는 정상적으로 실행되었지만, 프로그래머스에서 TC를 돌렸을때 시간초과가 발생하였다.
여러 방식을 시도해보다가 안되어서 다른 코드를 참고하였는데 포인트를 놓쳐서 많이 헤맸던 것 같다. 생각보다 단순한 문제였다ㅠㅠ..

이 문제에서 포인트는 동일한 자릿수라면 어떠한 숫자가 오든 가장 큰 수가 가장 앞에 오는것이 제일 큰 수라는 것이다.

문제 풀이

풀이는 stack과 순회를 이용하였다.
1. 빈 스택에 가장 먼저 조회되는 숫자를 담는다. 순차적으로 다음 인덱스에 위치한 숫자들을 담아주어야한다.
2. 만약, 스택의 마지막 숫자보다 큰 숫자를 만난다면 그 마지막 숫자 대신 큰 숫자가 들어가야하므로 변경되어야 하므로 기존 스택에서 pop()을 한다. 그리고 가장 큰 숫자가 가장 앞에 가야하므로 stack에 해당 숫자보다 큰 값이 없을때까지 pop()을 반복하며 숫자가 하나 빠질때마다 deleteCount를 차감한다.
3. 만약 stack이 비었거나 스택의 마지막값이 비교숫자보다 클 경우 스택에 비교숫자를 push()한다.
4. 정해진 k 즉 deleteCount이상으로 숫자를 pop()할 수 없으므로 deleteCount가 k와 일치하면 더이상 pop()을 진행하지 않고 push만 진행한다.
5. 마지막 숫자까지 모두 stack에 저장된다면 반복을 종료한다.
6. 최종 숫자의 길이는 초기 숫자의 length - k이므로, stack의 0~length-k 까지의 값만 추출한 후 반환한다.

코드

function solution(number, k) {
  let target = String(number);
  let stack = [];
  let deleteCount = k;
  let pt = 0;

  while (pt < target.length) {
    if (deleteCount && stack.length && target[pt] > stack[stack.length - 1]) {
      deleteCount--;
      stack.pop();
    } else {
      stack.push(target[pt++]);
    }
  }

  let len = target.length - k;
  let answer = stack.join("").slice(0, len);
  return answer;
}