[프로그래머스] 문자열 압축_Java

 

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

 

문제 풀이

1. 문자열 압축 시 압축할 수 있는 문자열의 단위는 1~ 문자열의 길이/2 사이의 값이다.

2. 문자열은 처음 시작 부분부터 압축할 단위의 크기대로 나누어 압축한다.

3. 문자열의 반복 횟수가 1일 경우 숫자는 생략하고, 1 이상일 경우 반복 횟수 + 반복 문자열로 압축할 수 있다.

4. 가장 짦은 압축 문자열의 길이를 반환한다.

 

 

코드

import java.util.*;
class Solution {
    public int solution(String s) {
        int len = s.length();
        int minLen = len;
        StringBuffer sb;
        
        for(int i=1; i<=len/2; i++){ 
            sb = new StringBuffer();
            
            int idx=0;
            while(idx<len){
                String str = s.substring(idx,idx+i);
                
                int cnt =1;
                while(idx+cnt*i < len &&
                          s.substring(idx+cnt*i).indexOf(str) == 0) cnt++;
            
                sb.append(cnt !=1 ?cnt+str : str);
                idx += cnt*i;
                
                if(idx+i>len) {
                    sb.append(s.substring(idx));
                    break;
                } 
            }
            minLen = Math.min(minLen, sb.toString().length());
        }
        return minLen;
    }
}

 

 

 

실행 결과