[プログラマー]貪欲(Greedy)-大数(JavaScript)の作成

問題の説明

ある数字からk個の数字を削除しようとしたときに得られる最大の数字を取得しようとします.
たとえば、2つの数字が1924から削除された場合、[19,12,14,14,92,94,24]を作成することができる.このうち最大の数字は94です.
解関数のパラメータとして文字列形式で与えられた数値と削除する数値kを用いる.solution関数を完了し、numberからk個の数値を削除したときに作成できる最大数値を文字列で返します.

せいげんじょうけん

は、2桁より大きく、100000桁未満の数字です.

kは、1または複数のビット数未満の自然数である.

I/O例

number
k
return
"1924"
2
"94"
"1231234"
3
"3234"
"4177252841"
4
"775841"

に答える

スタックを利用して解いてみます.積み重ねた後は入選に注意し、問題を解決します.絵を描きながら問題を解くともっとよく理解できます.

で除去可能な個数はk個であり、kがすべて消費されると、これ以上除去できない.

スタックは後入先出です.

ステージ

スタックに何も含まれていない場合、またはスタックに入れようとした数字がスタックの数字よりも小さい場合は、スタックに直接入れます.
上記の条件によれば、1がスタックに最初に挿入される可能性がある.

次の数字は9です.1と9に比べて9が大きいので、スタックには1が削除され、9が含まれます.
数字1は削除済みであり、削除可能な回数は1回(k:1)

のみである.

次の数字は2です.9と2に比べてスタック内の9が大きいので、2を9の後に置きます.削除された数字がないので、kは依然として1です.

以降の数字は4です.4は2より4の方が大きいのでスタックの最後の2を外して4を入れます.
削除可能個数はすべて消費される(kは0).

スタックの9と4を文字列に結合します.

コード#コード#

const number = "1924";
const k = 2;

function solution (number, k) {
  const numArr = number.split(''); // ["1", "9", "2", "4"]
  const stack = [];

  for (let idx in numArr) {
    
    // 스택에 있는 마지막 숫자가 스택에 넣으려는 숫자보다 작은 경우
    // 스택에 있는 마지막 숫자를 꺼내서 제거
    while ( stack.length > 0 && stack[stack.length - 1] < numArr[idx] ) {
      // console.log(stack[stack.length - 1], numArr[idx])
      if (k === 0) {
        // 제거할 수 있는 개수가 모두 소진됨 (k=0)
        // 더이상 숫자 제거할 수 없음
        break;
      } else {
        stack.pop();
        // 숫자 하나가 제거됐을 때
        // 제거할 수 있는 개수(k=2)에서 1씩 빼준다.
        k--;
      }
    }
    
    // [while 반복문 조건에 해당하지 않는 경우]
    // 스택에 아무것도 안 담겨있거나 or
    // 스택에 있는 숫자보다 스택에 넣으려는 숫자가 작거나 같은 경우 
    // 그냥 스택에 담는다.
    stack.push(numArr[idx]);
  }
	
  // 넣으려는 숫자가 스택에 있는 숫자보다 작으면 
  // 그냥 계속 담기므로 출력해야 하는 만큼 잘라서 사용
  stack.splice(stack.length - k, k);
  // 스택에 담긴 두 숫자를 합쳐 문자열로 만든다. 
  // ["9", "4"] -> "94"
  let answer = stack.join('');
  return answer; // "94"

}

solution(number, k);

問題のソース
https://programmers.co.kr/learn/courses/30/lessons/42883