My Solution

첫 for문에서 토큰을 구하는데, 토큰의 길이가 문자열 전체 길이의 절반을 넘어서면 반복될 수 없으므로 최대 len(s)//2길이의 토큰을 탐색한다.
두번째 for문에서는 문자열을 돌면서 토큰과 일치하면 카운터를 증가시키고, 일치하지 않으면 결과에 문자열을 담는다. 이후 반복이 종료되면 남은 문자열에 대한 처리를 하고 가장 짧은 문자열의 길이를 answer에 담아 유지한다.
문제 조건에서 문자열의 길이가 1000이하이기 때문에 총 반복횟수는 500*1000 = 500,000이하이므로 완전탐색으로 구현이 가능하다.

def solution(s):
    answer = len(s)
    now, repeat = "", ""

    for i in range(1, len(s)//2 + 1):
        result = ""
        repeat = s[:i]
        cnt = 0
        for j in range(len(s)//i):
            now = s[i*j:i*(j+1)]
            if now == repeat:
                cnt += 1
            else:
                if cnt > 1:
                    result += str(cnt) + repeat
                else :
                    result += repeat
                cnt = 1
                repeat = now

        if cnt > 1:
            result += str(cnt) + repeat
        else:
            result += repeat

        if len(s)%i != 0:
            result += s[-(len(s)%i):]
        answer = min(answer, len(result))

    return answer

Better Solution

프로그래머스에서 참고할만한 더 나은 답안이 있어 정리해봤다.

위의 solution은 문자열을 인덱스로 접근한 반면 아래 답안은 먼저 토큰을 나누어 리스트에 담고, zip()을 활용한 iterator로 접근하고 있다. 이때, for문에서 인접한 두 단어를 받기 위해 원본 리스트와 두번째 원소부터 시작하는 리스트를 zip()으로 묶었다. 두 리스트를 zip()으로 묶을 때 원소의 수를 맞추기 위해 두번째 리스트에 허수값인 ['']을 추가하였다.
또한 토큰을 만드는 과정도 range()의 3번째 인자로 토큰의 길이를 주면서 토큰의 길이대로 문자열을 나누고 있다.

def compress(text, tok_len):
    words = [text[i:i+tok_len] for i in range(0, len(text), tok_len)]
    res = []
    cur_word = words[0]
    cur_cnt = 1
    for a, b in zip(words, words[1:] + ['']):
        if a == b:
            cur_cnt += 1
        else:
            res.append([cur_word, cur_cnt])
            cur_word = b
            cur_cnt = 1
    return sum(len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)

def solution(text):
    return min(compress(text, tok_len) for tok_len in \
    list(range(1, int(len(text)/2) + 1))+ [len(text)])

-2020 KAKAO BLIND RECRUITMENT 문자열 압축