[백준] 2812번: 크게 만들기 (JavaScript, NodeJS)

문제

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

입력

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

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

출력

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

예제 입력 1 복사

4 2
1924

예제 출력 1 복사

94

예제 입력 2 복사

7 3
1231234

예제 출력 2 복사

3234

예제 입력 3 복사

10 4
4177252841

예제 출력 3 복사

775841

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const [n, number] = input;
const [length, count] = n.split(' '); 

// 문제 풀이:
function solution(length, count, number) {
	const splited = number.split('');
	const stack = [];

	for (let i = 0; i < length; i += 1) {
		const current = splited[i];

		// 스택이 채워져 있고, 스택의 Top이 현재 값보다 작고, count값이 있을 때 반복문을 돈다.
		while (stack.length && stack[stack.length - 1] < current && count) {
			// 위의 조건들이 만족된다면, 스택에서 pop, count - 1을 한다.
			stack.pop();
			count -= 1;
		}
		stack.push(current);
	}

	// 반례
	// 2 1
	// 21
	for (let i = 0; i < count; i += 1) {
		stack.pop();
	}

	return stack.join('');
}

// 제출
const answer = solution(length, count, number);
console.log(answer);

⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. 스택 이용
3. 단순히 앞 값과 뒷 값을 비교해서 넣는게 아니라, stack의 top이 현재 비교하는 값보다 클 때 까지 반복하는 것이 포인트
(테케: 4177252841)