반응형
문제
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)
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1092번: 배 (JavaScript, NodeJS) (0) | 2022.01.26 |
---|---|
[백준] 2212번: 센서 (JavaScript, NodeJS) (0) | 2022.01.26 |
[백준] 11000번: 강의실 배정 (JavaScript, NodeJS) (0) | 2022.01.25 |
[백준] 2839번: 설탕 배달 (JavaScript, NodeJS) (0) | 2022.01.24 |
[백준] 21314번: 민겸 수 (JavaScript, NodeJS) (0) | 2022.01.23 |