[テストエンコーディング]圧縮2020 KAKAO BLIND RECRUITMENT文字列
問題の説明
データ処理の専門家になりたい ピッチは文字列を圧縮する方法を学習しています.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.例えば、「aabbacc」については、「2 a 2 ba 3 c」と表すことができ(文字が1回繰り返されていない場合は1を省略する)、このような方式の欠点は、重複文字が少ない場合に圧縮率が低いことである.たとえば、文字列「abcabcdede」は完全に圧縮されません.この欠点を解決するために、「ピッチ」は、文字列を1つ以上の単位に切り取ることで圧縮し、より短い文字列として表す方法を探します.
たとえば、「abbcddababccdcdd」は、文字を1単位に切り取ると全く圧縮されず、2単位に切り取ると「2 ab 2 cd 2 ab 2 cd」と表すことができます.異なる方法で8単位でせん断および圧縮を行う場合、「2 abbcdcd」を使用して表すことができ、これは圧縮が最も短い方法である.
別の例は「abcabcdede」であり、文字を2単位に切り取って圧縮すると「abcabc 2 de」になり、3単位に切り取ると「2 abcdede」になり、この3単位が最も短い圧縮方法になります.3つの単位を切り取り、最後に残った文字列を貼り付けます.
圧縮する文字列sをパラメータとして指定する場合は、上述した方法に従って1つ以上の単位で文字列を切り取り、solution関数を完了して、表す文字列の中で最も短い長さを返します.
せいげんじょうけん
に答える
まず,アルゴリズムの最大時間複雑度を制限条件により推定した.一般的な処理ラインが1億未満の場合、効率テストに合格します.sの長さは最大1000であるため,最大時間複雑度はs 2 logss^2 logss 2 logs程度と推定できる.
まず最も簡単な方法で問題を解決する.圧縮文字列の結果を返す関数を抽象化する場合は、ソリューションを次のようにすべての単位に適用して最適な値を検索するように定義できます.
def solution(s):
answer = 1002
for i in range(1, len(s) + 1):
answer = min(answer, len(compress(s, i)))
return answercompress(s,i)=単位iで文字列sを圧縮します.
=前のi文字でできるだけ先に圧縮します.+残りの文字を単位iで圧縮する
=frontCompress(s,i)+compress(その他の文字、i)
compress(s,i)=frontCompress(s,i)+compress(left,i)compress(s,i) = frontCompress(s,i) +compress(left, i)compress(s,i)=frontCompress(s,i)+compress(left,i)
再帰関数にはもちろん条件文が必要です.字がどんどん短くなって、残りの字が単位より小さくなったら、そのままそのままそのまま運べばいいので、以下の条件を追加します.
compress(s,i)={sif len(s)
def compress(s,size):
if len(s)<size:
return s
front,left=frontCompress(s,size)
return front + compress(left,size)def frontCompress(s,size):
count=1
while s[0:size]==s[size*count:size*(count+1)]: count+=1
return s[0:size] if count==1 else str(count)+s[0:size], s[count*size:]完全なコード
def frontCompress(s,size):
count=1
while s[0:size]==s[size*count:size*(count+1)]: count+=1
return s[0:size] if count==1 else str(count)+s[0:size], s[count*size:]
def compress(s,size):
if len(s)<size:
return s
front,left=frontCompress(s,size)
return front + compress(left,size)
def solution(s):
answer = 1002
for i in range(1,len(s)+1):
answer=min(answer,len(compress(s,i)))
return answerKotlin.ver
import kotlin.math.min
class Solution {
fun solution(string: String): Int{
var ret=1002
for( i in 1..string.length){
ret= min(ret,string.compress(size = i).length)
}
return ret
}
fun String.compress(size:Int): String{
if(this.length<=size)
return this
val (front,left)=this.frontCompress(size)
return front+left.compress(size)
}
fun String.frontCompress(size: Int): List<String> {
var count=1
while(size*(count+1) <=this.length && this.substring(0,size)==this.substring(size*count,size*(count+1))) count++
return listOf(
if (count==1) this.substring(0,size) else count.toString()+this.substring(0,size),
this.substring(startIndex=count*size)
)
}
}Reference
この問題について([テストエンコーディング]圧縮2020 KAKAO BLIND RECRUITMENT文字列), 我々は、より多くの情報をここで見つけました https://velog.io/@jaeseong23/코딩테스트-2020-KAKAO-BLIND-RECRUITMENT문자열-압축-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol