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

입력되는 문자열을 압축해서 크기를 줄이는 파싱문제였습니다.

입력된 문자열의 반복되는 부분을 숫자로 바꾸어서 줄어든 문자열의 숫자를 리턴하면 되는 문제입니다.

example : "aabbaccc" 길이: 8 -> "2a2ba3c" 길이: 7

example2 : "abcabcabcabcdededededede" 길이: 24 -> "2abcabc2dedede" 길이: 14

example2 같은 경우는 여러 방법으로 자를 수 있는데

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

가장 짧게 줄어든 길이를 리턴하면 되는 방식입니다.

내 풀이

class Solution {
    public int solution(String s) {
        int limit = s.length() / 2;
        StringBuilder sb = new StringBuilder();
        StringBuilder temp = new StringBuilder();
        int min = s.length();
        for(int i = 1; i <= limit; i++) {
            sb.append(s);
            String pivot = sb.substring(0, i);
            sb.delete(0, i);
            int count = 1;
            while(pivot.length() <= sb.length()) {
                String newPivot = sb.substring(0, i);
                if(pivot.equals(newPivot)) {
                    count++;
                    sb.delete(0, i);
                } else {
                    if(count > 1)  {
                        temp.append(count);
                    }
                    temp.append(pivot);
                    count = 1;
                    pivot = newPivot;
                    sb.delete(0, i);
                }
            }
            if(count > 1) {
                temp.append(count); 
            }
            temp.append(pivot);
            temp.append(sb);
            min = Math.min(min, temp.length());
            temp.setLength(0);
            sb.setLength(0);
        }
        return min;
    }
}

풀이 설명

int limit = s.length() / 2;

문자열을 나누는 패턴의 크기는 주어진 문자열의 반으로 했습니다.

일단 substring의 패턴이 두번은 반복되야 문자열의 크기가 줄어드는데 패턴의 크기가 주어진 문자열의 크기의 1/2 이상인 것은 불가능하기 때문입니다.

StringBuilder sb = new StringBuilder();
StringBuilder temp = new StringBuilder();

StringBuilder를 두개 만들었습니다.

"sb" 는 패턴 비교시 나머지 문자열을 담아두는 용
(ex: 원래 문자열: "aabbacc" 현재비교패턴: "a" sb가 가지고 있는 나머지: "abbacc")

"temp"는 비교완료된 문자의 저장용
(ex: 원래 문자열: "aabbacc" 현재비교패턴: "b" temp가 가진 문자열: "2a")

min = Math.min(min, temp.length());

모든 크기의 패턴 비교 후 가장 작아진 길이의 결과 값을 가지고 있게 됩니다.

고수의 풀이

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);
    }
}

제가 두개의 stringbuilder를 사용한 부분을 재귀로 풀었네요. 원리는 같은것 같습니다. 다만 코드가 굉장히 간결하네요.