[Programmers] 문자열 압축 (Java)

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

문제 풀이

반복되는 문자열을 압축하여 최소 길이의 s를 구하는 문제로 모든 경우의 수를 구하여 최솟값을 갱신하는 방식으로 생각했습니다.

문자열의 길이 절반이상으로 끊으면 2번이상 반복될 수가 없으므로 문자열의 길이의 절반부터 1까지의 단위로 잘라서 비교했습니다.

우선, s의 길이가 1이면 무조건 1을 retrun 하기 때문에 처음에 따로 처리해주었습니다. n개 단위로 끊어서 반복되는 구간이 없으면 n만큼 길이를 더하고 반복되는 구간이 있으면 cnt를 증가시켜 몇 번 반복되는지 카운트 했습니다. 이 카운트를 기준으로 2, 10, 100, 1000(s의 길이는 1이상 1000이하)이 되었을 때 문자열 길이가 1개씩 늘어납니다. 이 숫자들을 구분하기 위해서 digit 변수를 선언 후 문자열로 변환한 길이가 변경되었을 때 문자열 길이를 늘려주었습니다.

코드

class Solution {
    public int solution(String s) {
        int sLen = s.length();
        
        // s의 길이가 1인 경우
        if(sLen == 1) return 1;
        
        // 끊을 단위의 수
        int len = sLen / 2;
        int answer = Integer.MAX_VALUE;
        
        while(len != 0) {
            int nowLen = 0;
            int cnt = 1;
            String temp = "";
            int digit = 0;
            
            for(int i = 0; i < sLen; i+=len) {
            	// 다음 반복되는 수를 찾기 위한 범위
                if(i+len <= sLen) {
                    String divStr = s.substring(i, i+len);
                    // 반복되는 경우
                    if(temp.equals(divStr)) {
                        cnt++;
                        if(digit != String.valueOf(cnt).length()) {
                            digit++;
                            nowLen++;                        
                        }
                    } else {
                    	// 반복되지 않는 경우
                        temp = divStr;
                        nowLen += len;
                        cnt = 1;
                        digit = 0;
                    }
                } else {
                	// 남은 문자열 더하기
                    nowLen += s.length()-i;
                }
            }
            
            answer = Math.min(answer, nowLen);
            len--;
        }
         
        return answer;
    }
}