[프로그래머스/Java] 60057번 문자열 압축

프로그래머스 문자열 압축 [2020 KAKAO BLIND RECRUITMENT]
https://programmers.co.kr/learn/courses/30/lessons/60057

단순 구현으로 접근할 수도 있으나, 재귀함수로 접근하는 멋진 풀이를 발견하고 포스트를 작성하게 되었다.

.
.

우선 내가 작성해 통과했던 코드는 다음과 같다.

class Solution {
    public int solution(String s) {
        int len = s.length();
        int answer = len;

        for(int i = 1 ; i <= len/2 ; i++){
            String result = "";
            int loop = len/i + (len%i == 0 ? 0 : 1);

            String lastString = s.substring(0, i);
            int lastCount = 1;

            for(int j = 1 ; j < loop ; j++){
                String thisString = s.substring(j*i, Math.min((j+1)*i, len));
                if(thisString.equals(lastString)) lastCount++;
                else if(lastCount == 1){
                    result += lastString;
                    lastString = thisString;
                } else {
                    result += lastCount + lastString;
                    lastString = thisString;
                    lastCount = 1;
                }
            }

            if(lastCount == 1) result += lastString;
            else result += lastCount + lastString;

            answer = Math.min(answer, result.length());
        }

        return answer;
    }
}

말 그대로, i만큼 문자를 잘라 lastString과 같다면 lastCount를 늘리고 다르다면 result에 lastCount와 lastString을 붙여 문자를 늘리는 방식이다.
'재귀'의 개념 자체를 도입하지 않은 이 코드는 loop를 몇 번 돌아야 할 지 미리 계산해야 했고, 앞 뒤 예외처리로 코드가 지저분한 편이다.

수행 시간은 다음과 같았다.

.
.

다음은 재귀의 개념을 도입한 코드로, loop에 대한 계산이 필요 없고 이전 결과를 저장하기 위한 별도의 변수 선언이 필요치 않다. 코드 자체도 훨씬 간결하다!

class Solution {
    public int solution(String s) {
        int len = s.length();
        int result = len;
        for(int i = 1 ; i <= len/2 ; i++)
            result = Math.min(result, getCompString(s, i, 1).length());
        return result;
    }
    public String getCompString(String s, int unit, int count){
        if(s.length() < unit) return s;
        String preString = s.substring(0, unit);
        String postString = s.substring(unit);
        if(postString.startsWith(preString)) return getCompString(postString, unit, count+1);
        return (count == 1 ? "" : count) + preString + getCompString(postString, unit, 1); 
    }
}

다만 수행시간에는 큰 차이가 없다. 함수를 반복적으로 호출하는 과정에서 매개변수, 리턴값 등을 스택 메모리에 올리는 과정이 반복되는 재귀함수의 특성 때문이다.