[백준/JS] 2812번. 크게 만들기

[백준] 2812번. 크게 만들기

1. 문제

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

2. 입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)
둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

3. 출력

입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다.

4. 풀이

• 스택은 오름차순 정렬을 할 수 있다.
• 현재 숫자와 스택 최상단의 값을 비교하여 현재 값이 더 크면 스택을 pop한다.
• pop하여 빠진 수는 지우는 K개 수 중 하나가 된다.
• 모든 숫자를 탐색한 후 k가 0이라면 알맞은 개수로 숫자를 지웠으니 신경 쓸 필요가 없다.
• k가 아직 남았다면 적절한 숫자를 찾기 못했단 말이기 때문에 뒤에서 남은 k개 만큼 지운다.
  • k는 while문을 돌면서 감소시켰기 때문에 처음 입력으로 주어진 k와 다른 k다.

5. 처음 코드와 달라진 점

• 모든 경우의 수를 나눠서 구현한 것을 통합 시켜 주었다.

6. 코드

function solution(n, k, num) {
  let answer;
  let stack = [];

  for (let i = 0; i < n; i++) {
    while (stack.length && stack[stack.length - 1] - num[i] < 0 && k) {
      stack.pop();
      k--;
    }
    stack.push(num[i]);
  }

  answer = stack.join("").substring(0, stack.length - k);
  return answer;
}