プログラマプログラマ:大きな数を作成するには


(質問リンク)

質問する


ある数字からk個の数字を削除しようとしたときに得られる最大の数字を取得しようとします.
たとえば、2つの数字が1924から削除された場合、[19,12,14,14,92,94,24]を作成することができる.このうち最大の数字は94です.
数値numberおよび削除する数値kは、解関数のパラメータとして文字列形式で与えられる.numberで、作成可能な最大数kを文字列で返すソリューション関数を完了します.
せいげんじょうけん
  • numberは、1桁以上100000桁未満の数字
  • kは、1桁未満の自然数です.
  • I/O例
    numberkreturn"1924"2"94""1231234"3"3234""4177252841"4"775841"

    に答える

    number前から最大値を選択します.number: 1231234k: 3の場合、1231234から4つを選択できます.
    文字列候補の最大値は、12312341231231234のうち4つを選択するので、少なくとも3つの後部座席を残し、可能な候補1231の中から最大の数字3を選択すると、残りの1234123421234の中から3つを選択するので、後の2つの可能な候補は12つである、最大2を除いて、残りの34343334のうち3つの選択肢しかなく、4444しか残っていません.
    実行時間を減らす努力.
    1.文字列(配列)を直接操作せずに、必要な値のみを抽出するためにインデックス値を保存
    2.最大の価格を選択するために、ループ文に9が表示されたら、すぐに中断します
    3.k個を十分に削除した場合、ナビゲーションを中止し、すぐに後の位置に戻る
    ソースコード
    function solution(number, k) {
        let answer = [];
        let startI = 0;
        
        // 앞에 고를 수 있는 숫자 중에 가장 큰 값 고르고, 그 다음 반복
        while (number.length > k) {
            let max = -1, maxI = -1;
            for (let i=startI; i<=k; i++) {
                if (max < number[i]) {
                    max = number[i];
                    startI = i+1;
                }
                // max가 9면 더 이상 찾을 필요 없으니까 break
                if (max === "9") break;
            }
            
            answer.push(max);
            k++;
            
            // 제거할 수 있는 수 다 제거했다면 뒷자리 이어서 return
            if (startI === k ) {
                return answer.join('') + number.substring(startI);
            }
        }
        
        return answer.join('');
    }