[Lv.2] 문자열 압축 : Java

 

프로그래머스

 

import java.util.*;

class Solution {
    public int solution(String s) {
        int n = s.length();
        if(n==1) return 1;  // 문자열 길이가 1인 경우 바로 1 리턴
        
        int answer = n; // 초기값은 원본 길이로 설정
        
        // 문자 조각 단위를 1~n/2까지 시도
        for(int k=1; k<=n/2; k++){
            StringBuilder sb = new StringBuilder();
            String pre = s.substring(0, k);
            int cnt = 1;
            
            for(int i=k; i<n; i+=k){
                int end = Math.min(i+k, n);
                String cur = s.substring(i, end);
                
                if(cur.equals(pre)){
                    cnt++;
                }
                else{
                    if(cnt>1) sb.append(cnt);
                    sb.append(pre);
                    pre = cur;
                    cnt=1;
                }
            }
            
            if(cnt>1) sb.append(cnt);
            sb.append(pre);
            
            answer = Math.min(answer, sb.length());
        }
        return answer;
    }
}