[プログラマ]文字列圧縮Python


質問する


https://programmers.co.kr/learn/courses/30/lessons/60057
データ処理の専門家になりたい「音声器」は、文字列を圧縮する方法を学んでいる.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
例えば、「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関数を完了して、表す文字列の中で最も短い長さを返します.

せいげんじょうけん

  • sの長さは1または1000以上です.
  • sには、アルファベット小文字のみが含まれています.
  • I/O例



    アイデア

  • で指定された文字1,2...、n個に切る
  • で切断された文字をtmpリストに追加し、さっき入力した文字列と同じ場合、tmpリストに追加せずにcntを追加します.
  • tmpリストでは、1以外の数字と、以前の答えの記憶値より小さい値が出力されます.
  • ソリューション関数python

    def solution(s):
        answer = 10000
        word = list(s)
        for i in range(1, len(word)+1):
            tmp = [[0]]
            new_list = [word[j:j+i] for j in range(0, len(word),i)]
            cnt = 1
            for k in range(len(new_list)):
                if tmp[-1] != new_list[k]:
                    tmp.append([str(cnt)])
                    tmp.append(new_list[k])
                    cnt = 1
                else:
                    cnt += 1
                if k == len(new_list)-1:
                    tmp.append([str(cnt)])
            del tmp[0]
            del tmp[0]
            tmp = sum(tmp,[])
            ans = 0
            for l in range(len(tmp)):
                if tmp[l] == "1":
                    ans += 1
            answ = len(''.join(tmp))-ans
            answer = min(answer, answ)
        return answer