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

문자열 압축

프로그래머스

 

• 내 풀이
  • 절반(n // 2)보다 크면 어차피 반복이 불가능
    • ⇒ size는 n // 2 + 1까지만 확인
  • size 단위로 잘라가면서 압축
    • 반복되는 부분은 count로 개수 세고, 새로운 문자열이 나오면 압축된 길이를 추가
    • 마지막 남은 부분까지 처리한 후 최소 길이를 갱신
  • 끝부분 더해지지 않을 수 있음
    • ⇒ size 단위로 잘라가면서 압축

def solution(s):
    answer=0
    def length_check(n):
        if n < 2:
            return 0
        elif n < 10:
            return 1
        elif n < 100:
            return 2
        elif n<1000:
            return 3
        return 4

    def compress(s):
        n = len(s)
        if n <= 1:
            return n

        min_length = n

        for size in range(1, n // 2 + 1):
            compressed = 0
            prev = s[:size]
            count = 1

            for i in range(size, n, size):
                curr = s[i:i + size]

                if curr == prev:
                    count += 1
                else:
                    compressed += length_check(count) + size
                    prev = curr
                    count = 1

            # 마지막 남은 부분 처리
            compressed += length_check(count) + len(prev)

            min_length = min(min_length, compressed)
            
        return min_length
    
    answer=compress(s)
    return answer