문자열 압축

수정 : 2024-07-02 [시간 복잡도 추가]

 

코딩테스트 연습 - 문자열 압축 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

나의 코드

# 2024-07-02
def solution(s):
    answer = 1000
    
    if len(s)==1:
        return 1
    
    for i in range(1,(len(s)//2)+1):
        result = ''
        check_dict = {}
        for j in range(0, len(s), i):
            now_value = s[j:j+i]
            if check_dict:
                if now_value in check_dict:
                    check_dict[now_value]+=1
                    continue
                else:
                    di_key, di_value = list(check_dict.items())[0]
                    if di_value==1:
                        result+=di_key
                    else:
                        result+=(str(di_value)+di_key)
                    check_dict.pop(di_key)
            check_dict[now_value]=1
        di_key, di_value = list(check_dict.items())[0]
        if di_value==1:
            result+=di_key
        else:
            result+=(str(di_value)+di_key)
        #print(result, check_dict)
        answer = min(answer, len(result))
        
    return answer

 

시간 복잡도 

1. for i in range(1,(len(s)//2)+1) : 문자열 길이를 하나씩 늘여가기에 선형시간 [ O(n) ]

2. for j in range(0, len(s), i) : 문자열 길이를 늘여가는 for문이 늘어날수록 시간이 절반으로 줄어드는 로그시간 [  O(logn) ]

3. 내부 딕셔너리 연산은 상수시간 [ O(1) ]

 

최종 시간 복잡도 : O(nlogn)