[프로그래머스] 문자열 압축, 파이썬

💡 문제 해결 아이디어

🛠 피드백

• 압축단위의 후보는 1부터 len//2까지 (꼭 나누어 떨어지지 않아도 된다)
• 각 압축단위에 대해서 문자열을 훑으며 압축문자열과 압축횟수를 저장한다!
• 총 압축된 길이는 "모든 (2 이상의 압축횟수의 길이)의 합 + 모든 (문자열의 길이)의 합"이다.
• 압축횟수가 1인 경우 즉 압축이 되지 않은 경우에는 압축횟수를 적지 않기 때문이다!

💻 작성된 코드(수정)

def solution(s):
	# 압축단위 후보는 1부터 len//2 까지 
    candi = [i for i in range(1, (len(s)//2+1))]
    # 정답의 upper bound는 압축을 하지 않은 케이스
    answer = len(s)
    
    # 각 압축단위에 대해서
    for length in candi:
        key = s[:length]
        shorten = []
        cnt = 1
        # 압축단위로 잘라서 압축을 진행하고
        # shorten에 압축문자열과 그 횟수를 저장한다.
        for  i in range(length, len(s), length):
            if key == s[i:i+length]:
                cnt += 1
            else:
                shorten.append([key, cnt])
                cnt = 1
                key = s[i:i+length]
        shorten.append([key, cnt])
        # 기존의 베스트 압축길이와 새로운 압축길이를 비교해 업데이트
        # 문자열의 길이는 항상 포함하되, 압축횟수의 길이는 압축횟수가 2 이상일 때만
        answer = min(answer, sum([len(key) + (len(str(cnt)) if cnt > 1 else 0) for key, cnt in shorten]))
    return answer