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

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   문자열이 주어질 때 문자열을 규칙에 따라 압축하여 표현한 문자열 중 가장 짧은 문자열의 길이를 구하는 문제이다. 예를 들어, "ababcdcdababcdcd"의 경우 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법이다. (1은 생략한다.) 제한 사항은 다음과 같다.

 

• 1 ≤ 문자열의 길이 ≤ 1,000
• 문자열은 알파벳 소문자로만 이루어져 있다.
• 문자열은 제일 앞부터 길이만큼 잘라야 한다.

---

접근 방식

   재귀의 개념을 이용해 문제를 해결하였다. 해결 방식은 크게 3가지 단계(압축 길이에 대한 재귀, 압축이 가능한 경우에 대한 처리, 압축이 불가능한 경우에 대한 처리)로 나눌 수 있다.

   먼저 압축 길이에 대해 재귀를 수행하는 단계를 알아보자. 압축 길이는 1개부터 가능하며 "최대 문자열의 길이 / 2"개까지 가능하다. (더 자세히는 압축을 수행하지 않은 경우도 포함된다.) 압축의 최대 길이가 문자열의 길이가 아닌 이유는 압축의 길이가 문자열의 길이의 반을 넘어가는 순간 압축이 불가능해지기 때문이다.

 

 

   이제 재귀 과정에 대해서 알아보자. 재귀 과정에선 문자열로부터 패턴과 타겟을 추출 및 비교하여 압축 가능 여부에 따라 다른 처리를 진행한다. 패턴은 문자열의 처음부터 패턴의 길이만큼, 타겟은 그 이후부터 패턴의 길이만큼 추출한다. 패턴과 타겟이 일치하는 경우 압축 count를 증가시키고 남은 문자열을 다음 재귀로 넘겨준다.

 

 

   패턴과 타겟이 불일치하는 경우가 발생하게 되면 현재 패턴과 남은 문자열들에 대한 처리가 진행되어야 한다. 즉, 현재 패턴을 만족했던 문자열들을 압축하였을 때의 길이를 구하고 남은 문자열은 다음 재귀로 넘겨준다.

 

 

   물론 처음부터 패턴과 타겟이 일치하지 않아 패턴의 count가 1인 경우도 존재할 수 있다. 이 경우 1은 생략되며 패턴의 길이만을 구하게 된다.

 

 

   이후 남은 문자열에 대해서도 같은 과정을 반복하게 되면 다음과 같이 길이가 구해지며, 현재 패턴은 자신이 만든 길이와 이후 패턴이 만든 길이를 더해 이전 패턴에게 전달하는 형태가 된다.

 

 

   재귀가 끝나는 타이밍에 대해서도 알아보자. 더 이상 패턴을 찾지 못하는 경우는 패턴과 타겟을 추출할 수 없는 경우다. 따라서 넘어온 '문자열의 길이'가 '패턴 + 타겟의 길이' 보다 작아지는 경우에 재귀는 종료된다. 이 시점에도 압축의 진행 여부를 고려하여 처리되어야 한다.

---

코드

class 프로그래머60057번 {

    public int solution(String s) {
        //압축을 하지 않은 경우를 최소값으로 초기화
        int min = s.length();

        //각 길이에 대해 압축을 진행하고 그 중 최소값을 저장
        //압축하려는 길이가 문자열 길이의 반을 넘어가는 경우 압축이 불가능
        for (int len = 1; len <= s.length() / 2; len++)
            min = Math.min(min, recursive(s, len, 1));

        return min;
    }

    public int recursive(String str, int len, int count) {
        //남은 문자열로는 압축이 불가능한 경우
        //Math.log10()로 숫자의 길이 반환
        //압축이 진행되는 도중이면 count 숫자의 길이 + 자신의 길이 반환
        //압축이 진행되지 않았으면 자신의 길이 반환
        if (str.length() < len * 2)
            return (count == 1 ? 0 : (int)Math.log10(count) + 1) + str.length();

        //압축할 패턴
        String pattern = str.substring(0, len);

        //남은 문자열
        str = str.substring(len);
        //패턴과 문자열의 앞에서 len만큼의 문자열 비교
        //패턴이 일치하는 경우 재귀 진행
        if (pattern.equals(str.substring(0, len)))
            return recursive(str, len, count + 1);

        //패턴이 일치하지 않는 경우
        //남은 문자열에 대해 재귀 진행
        //진행된 압축 수(count)의 숫자의 길이 + 현재 압축하는 길이
        return recursive(str, len, 1) + (count == 1 ? 0 : (int)Math.log10(count) + 1) + len;
    }
}