프로그래머스 : 문자열 압축 (자바, 파이썬)

프로그래머스

설계

• 주어진 문자열을 여러 길이 단위로 잘라서 각 단위별로 압축한 후 가장 짧은 압축 길이를 찾습니다.
• 문자열 압축 과정에서 동일한 문자열이 반복되는 경우 숫자를 이용하여 압축하고, 그렇지 않은 경우 원본 문자열을 사용합니다.
• 압축된 문자열의 최소 길이를 찾기 위해 모든 가능한 단위를 탐색하며, 각 단위별로 압축된 문자열의 길이를 계산하여 최소 길이를 갱신합니다.

구현

코드

자바(Java)

class Solution {
     public int solution(String s) {
        // 최솟값을 구하는 문제
        // 1~s.length 나눴을 때 최적으로 '압축된 문자열'의 길이 
        int min = s.length();

        // 문자열을 몇개로 쪼개서 나눌지 탐색
        // for (int i = 1; i <= s.length(); i++) {
        // 13 -> 6 (7) 1 + 나머지.
        for (int i = 1; i <= s.length() / 2; i++) {            
            // i = 압축되는 문자열 단위(범위)
            System.out.println(i);
            int tmp = 0; // 압축된 문자열의 길이
            
            // a b a b c d => i = 1, a / b/ a / b / c /d
            // i = 2, ab ab cd
            // 압축 단위로 탐색
            int start = 0; // 압축대상 문자열의 시작 인덱스
            while (start + i <= s.length()) {
                int end = start + i; // 압축대상 문자열의 종료 인덱스 + 1
                // substring 슬라이싱. 
                int count = 1; // 얼마나 현재 추출된 문자열이 반복되었는지
                String seg = s.substring(start, end); // 현재 압축단위만큼 추출된 문자열.
                System.out.println(seg);
            
                // 반복 여부를 체크
                while(end + i <= s.length() // i만큼 뒤에 커서를 움직여도 여전히 문자열 안에 있음
                     && seg.equals(s.substring(end, end + i))
                      // 현재 추출된 압축대상 문자열과 i만큼 이동한 다음 문자열이 일치하는가?
                     ) {
                    end += i; // 끝 커서를 움직여 주고
                    count++; // 2,3... count를 증가. (중복된 횟수 증가)
                }
                
                // while에서 벗어나거나 해당하지 않는다?
                // 더 이상 반복되는 문자열이 없다 (이 단위에서는...)
                System.out.println(count);
                if (count == 1) {
                    tmp += i; 
                } else {
                    tmp += i + ("" + count).length();
                }
                // 다음 탐색으로 이동
                start = end;
            }
            // 나머지 처리
            tmp += s.length() % i; // 남은 부분의 길이 추가
            
            System.out.println("this length : " + tmp);
            
            min = Math.min(min, tmp); // 최소 길이를 갱신
            System.out.println("now min : " + min);
        }
        return min;
    }
}

파이썬 (Python)

# import math
# import sys

def solution(s):
    # 최소값을 구하기 위해 가능한 가장 큰 값을 넣어놈
    # min_value = math.inf;
    # min_value = sys.maxsize;
    min_value = len(s) # 압축이 전혀 안되었을 경우
    
    # 문자열을 몇개로 쪼개서 나눌지 탐색
    for i in range(1, len(s) // 2 + 1):
        tmp = 0
        
        # 문자열을 단위로 쪼개서 탐색
        start = 0
        while start + i <= len(s):
            end = start + i
            count = 1
            seg = s[start:end]
            
            # 반복 여부 체크
            while end + i <= len(s)\
                and seg == s[end:end+i]:
                end += i
                count += 1
        
            # 압축 대상이 없거나 범위가 넘어간 경우
            if count == 1:
                tmp += i
            else:
                tmp += i + len(str(count))
            start = end # 다음 탐색 구간으로 이동
                
        # 문자열이 정확히 나눠지지 않는 경우 나머지 부분 처리
        tmp += len(s) % i

        min_value = min(min_value, tmp) # 최소 길이 갱신
        # min_value = min_value if min_value < tmp else tmp # 최소 길이 갱신

    return min_value