Computer >> 컴퓨터 >  >> 프로그램 작성 >> JavaScript

JavaScript에서 n 자리를 제거한 후 가장 작은 숫자

<시간/>

문제

두 개의 숫자를 취하는 JavaScript 함수를 작성해야 합니다. 이를 각각 첫 번째 및 두 번째 인수로 m 및 n이라고 합시다.

우리 함수의 임무는 숫자 m이 n자리를 제거한 후 가능한 가장 작은 숫자가 되도록 숫자 m에서 n자리를 제거하는 것입니다. 그리고 마지막으로, 함수는 숫자를 제거한 후 숫자 m을 반환해야 합니다.

예를 들어, 함수에 대한 입력이 -

인 경우
const m = '45456757';
const n = 3;

그러면 출력은 다음과 같아야 합니다. -

const output = '44557';

출력 설명:

가장 작은 수를 얻기 위해 5, 6, 7자리를 제거했습니다.

예시

이에 대한 코드는 -

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));

코드 설명:

우리는 여기에서 답을 공식화하기 위해 스택을 사용하는 욕심 많은 알고리즘을 사용했습니다. 왼쪽에서 오른쪽으로 입력 문자열 num의 각 값 el에 대해 스택에서 el보다 큰 최대 n개의 값을 제거한 후 el을 스택으로 푸시합니다.

숫자의 맨 왼쪽 위치가 맨 오른쪽 위치보다 더 가치가 있기 때문에 이 탐욕스러운 접근 방식은 맨 왼쪽 위치가 가장 작은 숫자로 구성되고 스택에 남은 것이 오른쪽에서 가장 큰 숫자가 되도록 합니다. 대부분의 위치.

입력 문자열 m이 처리된 후 제거할 n자리가 남아 있으면 맨 오른쪽 n자리가 가장 큰 자리이므로 맨 오른쪽 n자리를 제거합니다.

출력

콘솔의 출력은 -

44557