문제 정의
두 개의 값을 인수로 받는 JavaScript 함수를 작성해야 합니다. 첫 번째 인수는 숫자 문자열 m, 두 번째 인수는 제거할 자릿수 개수 n입니다.
함수의 목표는 숫자 m에서 n개의 자릿수를 제거하여, 제거 후 남은 숫자가 가능한 한 가장 작은 값이 되도록 만드는 것입니다. 그리고 최종적으로 자릿수를 제거한 결과를 반환해야 합니다.
예를 들어, 함수의 입력이 다음과 같다면 −
const m = '45456757';
const n = 3;
출력은 다음과 같아야 합니다 −
const output = '44557';
출력 설명
숫자 5, 6, 7을 제거함으로써 가장 작은 숫자인 '44557'을 얻을 수 있습니다.
구현 코드
이 문제는 아래와 같이 구현할 수 있습니다 −
const m = '45456757';
const n = 3;
const removeDigits = (m, n, stack = []) => {
let arr = m.split('').map(Number);
for(let el of arr){
while (n && stack.length && el < stack[stack.length - 1]){
stack.pop();
--n;
};
stack.push(el);
};
let begin = stack.findIndex(el => el > 0);
let end = stack.length - n;
return (!stack.length || begin == -1 || begin == end) ? "0" : stack.slice(begin, end).join('').toString();
};
console.log(removeDigits(m, n));
코드 설명
이 코드는 스택(stack)을 활용한 그리디(Greedy, 탐욕) 알고리즘으로 답을 구성합니다.
입력 문자열 m의 각 자릿수 el을 왼쪽에서 오른쪽으로 순회하면서, 현재 자릿수 el보다 큰 값들을 스택에서 최대 n개까지 제거(pop)한 뒤 el을 스택에 push합니다.
숫자에서는 왼쪽 자릿수가 오른쪽 자릿수보다 자릿값이 크기 때문에, 이 그리디 방식은 앞쪽 자릿수들이 최대한 작은 숫자로 채워지도록 보장합니다. 결과적으로 스택에 남은 값들은 뒤쪽 자릿수에 배치되는 상대적으로 큰 숫자들이 됩니다.
또한 입력 문자열 m을 모두 처리한 후에도 제거해야 할 n개의 자릿수가 남아 있다면, 오른쪽 끝의 n개 자릿수를 잘라냅니다. 오른쪽 끝의 자릿수들이 가장 큰 숫자들이기 때문입니다.
마지막에는 선행하는 0(leading zero)을 처리하기 위해 0보다 큰 첫 번째 자릿수의 위치를 찾아(begin), 해당 지점부터 유효한 숫자만 잘라내어 반환합니다. 만약 모든 자릿수가 제거되어 빈 값이 된다면 "0"을 반환합니다.
실행 결과
콘솔에 출력되는 결과는 다음과 같습니다 −
44557