[프로그래머스] 문자열 압축

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

---

풀이 과정

문자열을 몇 개 단위로 잘라서 압축해야 가장 짧은 문자열이 되는지 그 길이를 구하는 문제.

 

어떻게 하면 가장 짧은 압축 문자열을 구할 수 있을까??

 

aaaabbbbaaaabbbb는 8개 단위로 자르면 2aaaabbbb이고 4개 단위로 자르면 4a4b4a4b이다. 4개 단위로 잘랐을 때 압축 문자열이 더 짧다.

무조건 큰 단위로 자른다고 짧은 문자열이 되는 것이 아니기 때문에 다 구해봐야 알 수 있다.

 

k개 단위로 자른다고 할 때, 1 ~ len(문자열) // 2 + 1 범위로 잘라 문자열을 만들어 답을 구할 수 있다.

 

k는 전체 문자열 길이의 반을 넘을 수는 없습니다. 넘으면 압축 되는 경우가 없기 때문 

 

1. 문제를 이해하고나서 슬라이싱을 떠올렸다.
2. for문을 통해 n개의 단위로 압축 기준을 설정하며 각각의 압축 개수를 카운팅 했다.
3. 비교가 끝난 문자열은 임의로 만든 res 변수에 문자열로 합치고 원본 문자열 s에서 제거.
4. 가장 큰 for문 (자르는 i개 단위 설정 부분)이 끝날 때마다 answer에 넣고 마지막에 answer의 min값을 리턴.

---

def solution(s):
    answer = []
    if len(s) == 1:
        return 1
    for i in range(1, len(s)//2+1):
        res = ''
        cnt = 1
        tmp = s[:i] ## i개 단위로 자르기
        
        for j in range(i, len(s)+i, i):   ## i씩 증가하며 슬라이싱
            if tmp == s[j:i+j]:           ## 같으면 cnt 증가
                cnt += 1
            else:                         ## 더 이상 반복되지 않으면 
                if cnt == 1:              	## 한 번도 반복되지 않은 경우 그대로 누적 합치기
                    res += tmp     
                else:
                    res = res + str(cnt) + tmp ## 체크 끝난 문자열 누적 합치기
                tmp = s[j:i+j]                 ## 반복되지 않으므로 원본에서 제거
                cnt = 1
        answer.append(len(res))  ## 문자열 길이 저장
                    
    return min(answer)