Programmers#문자열 압축

---

LEVEL :

Level2

---

문제 요약 :

2020년 카카오톡 코딩테스트 제출 문제이다.

주어진 문자열을 문제에서 주어진 방법으로 압축하여 최소 길이를 구하는 문제였다.

---

해결 방안 :

별다른 방안없이 1~len(string)/2 까지의 길이로 압축하는 방법을 모두 구현해보아야 최소 압축 길이를 구할 수 있다.
다만 주의 해야 할 점은 압축할때 중복 갯수가 일의 단위이면 예를들어 5번중복되면 5abc , 10번 중복되면 10abc , 100번 중복되면 100abc가 되기에 단위마다 압축길이가 달라지는 점을 유의해야 한다.

---

시간 복잡도 :
N = string의 길이
O(N**2)

---

Solution

def solution(s):
    slen = len(s)
    minlen = slen
    for i in range(1,slen//2+1) :
        start = 0
        cnt = 0
        temp = ""
        newlen = slen
        for n in range(0,slen,i) :
            if temp == s[n:n+i] :
                cnt += 1
                last = n+i 
            else :
                if cnt != 0 :
                    compact = len(temp) + len(str(cnt+1))
                    newlen = newlen - (last-start) + compact
                    cnt = 0                    
                temp = s[n:n+i]
                start = n
        if cnt != 0 :
            compact = len(temp) + len(str(cnt+1))
            newlen = newlen - (last-start) + compact
        minlen = min(minlen,newlen)
    return minlen

---

출처

프로그래머스 : https://programmers.co.kr/learn/courses/30/lessons/60057