[Python] 프로그래머스 : 문자열 압축 (구현, 완전탐색)

[2020 카카오 블라인드 채용]
https://programmers.co.kr/learn/courses/30/lessons/60057

머리말

딱 구현 문제라고 느껴져 문제를 잘 해석하려고 노력하였다.
하지만, 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 이 문장을 과소평가하여 첫 제출 때 틀렸다.
그리고 올바르게 짠 것 같은데 자꾸 72점이 나와 다른 사람의 코드를 참고할까 하다가 끝까지 디버깅하여 결국 풀어냈다.

코드

의식의 흐름대로 작성하여 코드가 난잡합니다 🤢

def solution(s):
    answer = [len(s)]

    for cut in range(1, len(s) // 2 + 1): # 자를 수 있는 범위 (최소 2개 최대 절반개)
        substrIdx = 0
        cutstr = '' # 압축된 문자열을 임시저장
        while substrIdx < len(s):
            substr = s[substrIdx:substrIdx+cut] # 압축의 기준이 되는 문자열
            count = 1 # 압축 횟수
            for checkIdx in range(substrIdx + cut, len(s) - cut + 1, cut):
                checkstr = s[checkIdx:checkIdx+cut] # 동일한 문자열인지 확인하는 문자열
                if substr == checkstr:
                    count += 1
                    substrIdx += cut # 압축했으면 중복으로 확인하면 안됨
                else: break
            if count != 1: # 압축 문자열
                cutstr = cutstr + str(count) + substr
            elif len(substr) == cut: # 압축되지 않는 문자열
                cutstr = cutstr + checkstr
            else: # 압축되지 않는 문자열의 나머지 문자열
                cutstr = cutstr + substr
            substrIdx += cut

        answer.append(len(cutstr))

    return min(answer)

다른 해설

[이것이 코딩 테스트다]의 해설은 다음과 같다.

def solution(s):
    answer = len(s)

    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for step in range(1, len(s) // 2 + 1):
        prev = s[0:step]
        compressed = ""
        count = 1
        # step 크기만큼 증가시키며 이전 문자열과 비교
        for j in range(i, len(s), i):
            # 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j + step]:
                count += 1
            # 다른 문자열이 나왔다면 (압축 못하는 경우)
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j+step] # 다시 상태 초기화
                count = 1
        # 남아 있는 문자열 처리
        compressed += str(count) + prev if count >= 2 else prev
        answer = min(answer, len(compressed))
    return answer