문제 접근

브루트포스로 모든 경우를 다 고려해보고 최소길이를 구하면 되는 문제다.
어차피 문자열의 길이는 1000자이고, 압축단위를 키워갈수록 그만큼 순회하는 횟수도 비례해서 줄어들게 된다.

다만, 이 문제에 가지치기를 적용해서 개선하고 싶었으나, StringBuilder를 쓰고 있어서 문자열 길이를 중간에 구하는 비용이 너무 컸다. 실제로 가지치기 로직을 넣으니 시간이 더 오래걸렸다.

문제 풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        for(int i=1; i<=s.length(); i++) {
            answer = Math.min(answer, compression(s, i));
        }
        return answer;
    }
    
    int compression(String s, int size) {
        int sizeCount = s.length() / size;
        int remainCount = s.length() % size;
        StringBuilder sb = new StringBuilder();
        String pattern = "";
        int patternCount = 0;
        for(int i=0; i<sizeCount; i++) {
            int sIndex = i*size;
            String curString = s.substring(sIndex, sIndex+size);
            if(pattern.equals(curString)) {
                patternCount++;
            } else {
                if (pattern.length() > 0) {
                    if (patternCount > 1) sb.append(patternCount);
                    sb.append(pattern);
                } 
                pattern = curString;
                patternCount = 1;
            }
        }
        if (pattern.length() > 0) {
            if (patternCount > 1) sb.append(patternCount);
            sb.append(pattern);
        } 
        
        sb.append(s.substring(sizeCount*size, s.length()));
        return sb.toString().length();
    }
}

이제 프로그래머스에 올라온 카카오 기출 약 절반 정도를 풀었다. 남은건 거의 레벨3이기 때문에 앞으로 구현 실력을 더 끌어올릴 수 있을 것 같다.