[프로그래머스 Lv.2] 문자열 압축 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

풀이

반복되는 패턴을 찾을 것이기 때문에 가장 긴 반복되는 패턴의 길이는 무조건 전체 문자열의 길이의 절반 이하 일 수밖에 없다. 그렇기에 전체 문자열의 길이의 절반부터 길이 1까지 반복하며 반복되는 패턴의 수를 체크하고 압축 시의 길이를 체크하면 된다.

def solution(s):
    length = len(s) # 문자열의 길이
    answer = 1001 # 최대 문자열의 길이가 1000이기에 반드시 압축한 문자열의 길이는 1001보다 작을 수 밖에 없음
    
    if length == 1: # 문자열의 길이가 1이면 압축할 것이 없기에 그대로 길이는 1
        return 1
    
    for i in range(len(s) // 2, 0, -1): # 패턴이 나올 수 있는 최대 길이부터 1까지 반복
        pre = "" # 반복된 패턴
        new_length = 0 # 압축한 길이
        cnt = 1 # 반복된 횟수
        
        for j in range(0, length + 1, i): # 인덱스 0부터 끝까지 i만큼 키워가면서 반복
            tmp = s[j:j+i] # 문자열을 원하는 크기로 처음부터 슬라이싱
            if pre == tmp: cnt += 1 # 만약 이전 패턴과 동일하다면 반복된 횟수 1 증가
            elif pre != tmp: # 만약 이전 패턴과 다른 경우
                new_length += len(tmp) # 현재 슬라이싱한 문자열의 길이만큼 업데이트
                if cnt > 1: new_length += len(str(cnt)) # 만약 이전에 슬라이싱한 문자열이 반복된 패턴이라면 반복된 횟수의 길이만큼 업데이트
                cnt = 1 # 반복된 횟수 초기화
                pre = tmp # 현재 슬라이싱한 문자열을 패턴으로 등록하여 다음 슬라이싱한 문자열과 비교할 수 있도록 함
        answer = min(answer, new_length) # 최솟값으로 업데이트
    return answer