[백준] 2812 크게 만들기 - javascript

📌 문제

https://www.acmicpc.net/problem/2812

📌 풀이

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, k] = input[0].split(" ").map(Number);
let arr = new Array(n);
arr = input[1].split("").map(Number);
let stack = [];
let cnt = k;
for (let i = 0; i < arr.length; i++) {
  if (stack.length === 0) {
    stack.push(arr[i]);
  } else {
    while (cnt > 0 && arr[i] > stack[stack.length - 1]) {
      stack.pop();
      cnt--;
    }
    stack.push(arr[i]);
  }
}
while (cnt > 0) {
  stack.pop();
  cnt--;
}
console.log(stack.join(""));

✔ 알고리즘 : 스택

✔ 문자열을 배열로 만든 후 배열을 탐색하며 스택의 상단과 비교

✔ 지울 수 있는 횟수(cnt)가 양수이고 상단과 비교했을 때 현재 수가 더 큰 경우 스택의 상단 pop

✔ 상단이 현재 수 보다 크거나 cnt가 0이되면 현재 수 stack에 push

❗ 배열을 모두 탐색했는데 cnt가 양수인 경우
현재 stack이 오름차순이지만 제거해야되는 수가 존재하는 경우이다.
따라서 맨뒤에서부터 남은 cnt횟수만큼 제거해야 한다.

✔ 난이도 : 백준 기준 골드 5