(Javascript) 백준 2812번 : 크게 만들기

 

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

2812번: 크게 만들기

문제

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

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000)

둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다.

출력

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

---

스택을 활용한 그리디 문제. 숫자를 뽑아서 스택에 넣어주면서, 스택의 꼭대기에 있는 값이 넣으려는 값보다 큰 경우 빼준다. 넣으려는 값보다 작은 값이 없어서 K개를 빼지 못했을 경우를 생각해서, K개보다 적게 뺐다면 그냥 빼준다

const fs = require('fs');
const input = fs.readFileSync('./input.txt').toString().split('\n').map(item=>{return item.trim()});
const [N, K] = input[0].split(' ');
const number = input[1];
const stack = [];
let count = 0;
for (const item of number) {
    while(count < K && stack[stack.length -1] < item) {
        stack.pop();
        count++;
    }
    stack.push(item);
}
while(count < K){
    stack.pop();
    count++;
}
console.log(stack.join(""));