📝 質問する

問題の説明

データ処理の専門家になりたい「音声器」は、文字列を圧縮する方法を学んでいる.最近,文字列に連続的に現れる同じ値を文字数と繰返し値として表すことによって,より短い文字列に減少する簡単な無損圧縮法を学習した.
例えば、「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例

sresult"aabbaccc7"ababcdcdababcdcd"9"abcabcdede"8"abcabcabcabcdededededede"14"xababcdcdababcdcd"17

📌コード#コード#

package programmers;

public class KakaoStringCompress {

    public static int solution(String s){
        int answer = s.length();
        for(int i = 1; i <= s.length(); i++) {
            int result = i;
            String temp = s.substring(0,i);
            int cnt = 1;
            for(int j = i; j < s.length(); j+=i){
                String curStr = "";
                if(j+i >= s.length()) curStr = s.substring(j);
                else curStr = s.substring(j, j+i);

                if(curStr.equals(temp)){
                    cnt++;
                    if(cnt==2) result += 1; //같은 문자열이 나오면 한번만 1 증가시키면 됨
                    else if(cnt==10) result += 1;
                    else if(cnt==100) result += 1;
                    else if(cnt==1000) result += 1;
                }
                else{
                    cnt = 1;
                    temp = curStr;
                    result += curStr.length();
                }
            }
            if(result < answer) answer = result;
        }

        return answer;
    }
	//아래는 테스트용 main 메서드
    public static void main(String[] args) {
        System.out.println(solution("ababababcasdksadkjfas"));
    }

}

解答方法

まず、問題は完了した文字列ではなく、文字列の長さです.そこで,圧縮文字列を作成する方法に加えて,文字列長を記録する方法を試みた.
文字列を一定の単位で遮断して圧縮できる場合、圧縮された部分は(単位長+1)lengthを有する.(+1は何回繰り返したかを示す)
当初,同じ文字列を10回以上繰り返すとは思わなかったため,コードをコミットする際,精度スコアは72点であった.
その後、同じ文字列が10回以上、100回以上、1000回以上繰り返される可能性があるという事実が脳をかすめ、その部分を追加した.
個人的にその部分を整理したいのですが、うん...知りません😅
(感謝文字列の長さは1000まで)