문자열 압축

• 그냥 무식하게, 문자를 1개단위, 2개단위, …, |s|개 단위로 모두 압축해보고, 그중에서 가장 길이가 짧은것을 찾으면 된다.
  • 단위가 전체 길이의 절반을 넘어가면 압축이 불가능하므로, |s|/2 까지만 해봐도 되긴 하다만, 큰 의미는 없다.
• i개 단위로 압축을 해볼때 걸리는 시간은, i값에 관계 없이 O(log|s|) 이다. 따라서 전체 시간 복잡도는 O(|s|*log|s|).
• 실수하기 쉬운 부분은, i개 단위로 압축할 때 i길이의 문자열이 x번 반복된다면 압축된 길이는 i+1 이 아니라, i + len(str(x))이다. x가 1자리수보다 클 경우도 생각해야 한다는 의미이다.

"""Solution code for "Programmers 60057. 문자열 압축".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/60057
- Solution link: http://www.teferi.net/ps/problems/programmers/60057
"""

import itertools


def chars(group, size):
    count = sum(1 for _ in group)
    if count > 1:
        return size + len(str(count))
    else:
        return size


def solution(s):
    answer = len(s)
    for size in range(1, len(s)):
        pieces = (s[pos:pos + size] for pos in range(0, len(s), size))
        length = sum(chars(g, len(k)) for k, g in itertools.groupby(pieces))
        answer = min(answer, length)
    return answer