実施-3.文字列圧縮

質問する

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

sresultaabbaccc7abcabcdede9abcabcdede8abcabcabcabcdededededede14xababcdcdababcdcd17

I/O例説明

I/O例#1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

I/O例#2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

I/O例#3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

I/O例#4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

I/O例#5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

インプリメンテーションコード

  
import java.io.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();
        for(int i = 1;i <=s.length()/2 ; i++){
			String compressed = "";
			String prev = s.substring(0,i);
			int cnt = 1;
			for(int j = i; j < s.length(); j+=i ){
				String str = "";
				for(int k = j;k < i+j; k++){
					if(k <s.length()) str += s.charAt(k);
				}
				if(prev.equals(str)){
					cnt++;
				}else{
					compressed += (cnt>= 2) ? cnt+prev : prev;
					cnt = 1;
					prev = str;
				}
			}
			compressed += (cnt >= 2)? cnt + prev : prev;
			answer = Math.min(answer, compressed.length());
		}
        
        return answer;
    }
}

public class Main {

	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s = br.readLine();
		Solution sol = new Solution();
		int count = sol.solution(s);
		System.out.println(count);
	}

}
  

コード解釈

実装の方法は容易に考えられるが,本当に実装コードは難しい.これは問題を体現すると同時にずっと混同されている問題である.まず1～長さ/2を繰り返します
いいですよ.そして0点からiまで.そして、これらの文字をiからi+iと比較し、正しければcnt++が違うことを確認して1かどうかの後、文字列に値を加えればよい.
それから長さを求めればいいので、最小値を求めます.