製造大数(貪欲法、プログラマー)

大数の作成

📌 問題の説明

ある数字からk個の数字を削除しようとしたときに得られる最大の数字を取得しようとします.

たとえば、2つの数字が1924から削除された場合、[19,12,14,14,92,94,24]を作成することができる.このうち最大の数字は94です.

解関数のパラメータとして文字列形式で与えられた数値と削除する数値kを用いる.solution関数を完了し、numberからk個の数値を削除したときに作成できる最大数値を文字列で返します.

📌せいげんじょうけん

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

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

🤔 初めて問題に遭遇したとき、サンプルnumberをよく見なかった.長さ−k個数の重複しない最大数を作れば良いと思います.
だからDFSで순서가 없는の最大数を作りたいです.

	function solution(number, k) {
  let answer = Number.MIN_SAFE_INTEGER;

  let numberLength = number.length - k;
  let ch = Array.from({length: number.length}, ()=> 0);
  const DFS = (L, sum) => {
      if ( L === numberLength) {
        console.log(sum)
        answer = Math.max(answer, sum)
      }
      else {
          for ( let i = 0; i <= number.length; i++ ) {
              if ( ch[i] === 0 ) {
                  ch[i] = 1;
                  DFS(L+1, sum + number[i])
                  ch[i] = 0
              }
          }
              
      }
  }
  DFS(0, 0)

  return answer
}


console.log(solution("1924", 2)) // "94"
console.log(solution("1231234", 3)) // "3234"
console.log(solution("4177252841", 4)) // "775841"

😵‍💫 数を作成し、コードを迂回して値を表示してから、これが間違っていることに気づきました.
テストケース関数出力:作成したソリューション(「1924」,2)9494ソリューション(「1231234」,3)32344332ソリューション(「417725241」,4)775841877544
つまり、私が作った数は重複せず、順序を考慮しない組み合わせの中で最大の数조합であり、問題では順序を考慮しない最大数순열が与えられる.
また,複雑度を最小限に抑えるためには,貪欲法を用いてO(n)時間複雑度を用いることが考えられる.
したがって,for文で1回の探索を行い,スタック内の対応する数字をpushし,前の数字より小さい場合には除外とkの数を1に減らすコードを適用した.

function solution(number, k) {
    const stack = [];

    for ( let i = 0; i < number.length; i++ ) {
        const el = number[i];
        while ( k > 0 && stack[stack.length - 1] < el ) {
            stack.pop();
            k--;
        }
        //  stack.push(el);
        // 동일한 수가 연속되었을 때 모든 수가 푸쉬되는 경우를 제외하기 위해
        // number.length에서 k만큼 제거 된 숫자가 스택안에 존재하는 경우는
        // 더 이상 푸쉬 하지 않는다.
        if (stack.length < number.length - k ) stack.push(el);
    }
    // console.log(stack)
    console.log(k)
    return stack.join('');

}

// console.log(solution("1924", 2)) // "94"
// console.log(solution("1231234", 3)) // "3234"
// console.log(solution("4177252841", 4)) // "775841"
// console.log(solution("55555", 2)) // "555"

// 테스트 케이스에는 없는 예외 케이스
// console.log(solution("333355", 3)) // "355"

💡 しかし、何の条件もなくスタックに数字を入れると、同じ数字が連続して現れるとwhile文の条件に入ることができず、kがいくらであってもスタックからポップアップ()できません.(テスト12に失敗)

この要件を満たすために、スタックに表示された数と同じ数が含まれている場合は、次の数がスタックに入れない条件が追加されます.