大数の作成(Programmers 42883)

🧑‍💻 大数の作成

問題の説明

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

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

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

せいげんじょうけん

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

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

👀 I/O例
numberkreturn"1924"2"94""1231234"3"3234""4177252841"4"775841"

🧑‍💻 解決策

配列を利用しようとしたが,2番目のテストケースを回してみると,組合せの形式ではなくスタックである.

スタックを用いて解読することに気づいた.

🧑‍💻 失敗コード

from itertools import permutations

def solution_fail(number, k):
   number = list(number)
   permu = list(permutations(number, len(number) - k))
   next = []
   an = [None for r in range(len(permu))]

   for i in permu :
       next.append(list(i))

   for i in range(len(next)) :
       chk = "".join(next[i])
       an[i] = chk

   an = list(map(int, an))
   answer = str(max(an))

   return answer

🧑‍💻 コード#コード#

def solution(number, k) :
   stack = []

   for i in number :
       while stack and i > stack[-1] :
           if k > 0 :
               stack.pop()
               k -= 1
           else :
               break

       stack.append(i)

   if k > 0 :
       for i in range(k) :
           stack.pop()

   answer = "".join(stack)
   return answer

🧑‍💻 総評

久しぶりに

を解いて、また難題を解こうとする事故が発生しました.

「簡単が一番」

を忘れないでください.