[알고리즘] 문자열 압축

포인트

• 구현 문제를 풀었을 때, 그것만큼 또 희열이 있는 것이 몇 없을 것 같습니다. 하지만 틀리면 그냥 기분이 나쁩니다. 문제에서 주어줬듯이 문자열 압축을 고민하는 문제 입니다. (허프만 알고리즘이 떠오릅니다.)
• for loop 구간에서 len(s)//2+1 만 순회를 하여도 성립하는 이유는 그 이후를 돌면 어차리 원본 값이 나오기 때문에 할 필요성이 없어서 입니다. 

🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. 

python

def add(cnt: int, before: str) -> str:
    return before if cnt == 1 else str(cnt) + before


def check(s: str, unit: int) -> int:
    temp = ''
    before = s[:unit]
    # 시작구간 설정
    cnt = 1
    for i in range(unit, len(s), unit):
        current = s[i:i + unit]
        # 현재 단어
        if before == current:
            # 이전 단어와 현재 단어가 같다면 count+=1
            cnt += 1
        else:
            temp += add(cnt, before)
            cnt = 1
            # 다를 경우 카운트 1 초기화
        before = current
        # 이전 값을 현재 값으로 바꾸기
    else:
        # 전부 끝났는데 cnt 가 남아있다.
        temp += add(cnt, before)
    return len(temp)


def solution(s: str) -> int:
    answer = 987654321
    if len(s) == 1:
        # 1일 경우는 무조건 1이다.
        return 1

    for i in range(1, len(s) // 2 + 1):
        # 반 이상이 넘어가는 경우는 고려할 필요가 없다. 어차피 성립하지 않는다.
        result = check(s, i)
        answer = min(answer, result)
    return answer