프로그래머스 - 문자열 압축

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 문자열 압축

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

풀이 1 : 재귀를 이용하여 문자열 탐색

class Solution {
    public int solution(String s) {
        int answer = 0;

        for(int i=1; i<=(s.length()/2)+1; i++){
            int result = getSplitedLength(s, i, 1).length();
            answer = i==1 ? result : (answer>result?result:answer);
            // 더 적은 수의 문자를 출력
        }

        return answer;
    }

    public String getSplitedLength(String s, int n, int repeat){
        if(s.length() < n) return s;
        String result = "";
        String preString = s.substring(0, n);
        String postString = s.substring(n, s.length());

        // 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
        if(!postString.startsWith(preString)){
            if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
            return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
        }

        return result += getSplitedLength(postString, n, repeat+1);
    }
}

풀이 2 : 문자열을 하나하나 점검

class Solution {
    public int solution(String s) {
        int min = s.length();
        int len = s.length()/2+1;
        // 문자열 자르는 단위 = i
        for(int i = 1; i < len; i++) {
            String before = "";
            int sum = 0;
            int cnt = 1;
            // 문자열 자르는 시작 지점 = j
            for(int j = 0; j < s.length();) {    
                // j에서 j+i만큼 문자열 자르기
                int start = j;
                j = (j+i > s.length()) ? s.length():j+i;
                String temp = s.substring(start, j);
                // 이전 문자열이랑 비교
                if(temp.equals(before)) {
                    // 문자열이 같으면 cnt++
                    cnt++;
                } else {
                    // 문자열이 다르면
                    // 숫자 길이를 sum에 더해준다
                    if(cnt != 1) {
                        sum += (int)Math.log10(cnt)+1;
                    }
                    // cnt는 1로 초기화
                    cnt = 1;
                    // 이전 문자열을 sum에 더해준다
                    sum+=before.length();
                    // 앞의 문자열을 이전 문자열로 설정
                    before = temp;
                }
            }
            // 문자열 길이 + 숫자 길이
            sum+=before.length();
            if(cnt != 1) {
                sum += (int)Math.log10(cnt)+1;
            }
            // 짧은 문자열 길이 분별
            min = (min > sum) ? sum : min;
        }

        return min;
    }
}