프로그래머스 Lv2 문자열 압축 Python

문제 링크

1. 2020 KAKAO BLIND RECRUITMENT

코딩테스트 연습 | 프로그래머스 스쿨

정답코드

def solution(s):
    length = len(s)
    if length == 1:
        return 1
    minLength = 1001
    for l in range(1, length//2+1):
        lString = ""
        prevString = ""
        cnt = 0
        for idx in range(0, length, l):
            string = ""
            if idx+l > length:
                string = s[idx:]
            else:
                string = s[idx:idx+l]
            
            if string == prevString:
                cnt += 1
            else:
                if cnt:
                    lString += str(cnt+1) + prevString
                else:
                    lString += prevString
                prevString = string
                cnt = 0
        if cnt:
            lString += str(cnt+1) + prevString
        else:
            lString += prevString
        lenString = len(lString)
        if minLength > lenString:
            minLength = lenString
        
    answer = minLength
    return answer

느낀점 & 풀이방법

 사실 이정도 쉬운 문제까지 글을 써야 하나 싶었지만 뭔가 핵심이라고 할만한 부분을 찾아서 글을 적어본다. 예전이었으면 떠올리지 못했을 부분 for l in range(1, length//2+1). 글자 길이가 9인 문자열이 있다고 하자. 글자수 5로 압축한다고 하면 될까? 어림도 없다. 5 랑 4로는 압축할 수 없다. 4와 4 + 1로 압축은 가능하다. 따라서 2로 나눠서 시간복잡도를 낮췄다. 추가적으로 for idx in range(0, length, l) 이 부분도 연습하지 않으면 바로 떠오르지 않는다. 뇌가 굳어서 안 떠올랐다면 그냥 range(0, length)로 만들고 if로 인덱스값이 유효한지를 확인했을 것 같다.