[Programmers] Level 2. 문자열 압축

🔗 Problem Link

프로그래머스

---

❔Thinking

• 주어진 문자열을 1개 이상의 일정한 단위로 잘라 압축한 문자열 중, 가장 짧은 문자열의 길이를 반환한다. 

---

💻Solution

def solution(s):
    INF = int(1e9)
    answer = INF
    n = len(s)
    for i in range(1, n+1):
        tmp = ''
        prev = s[:i]
        cnt = 1
        for idx in range(i, n, i):
            now = s[idx:idx+i]
            if prev == now:
                cnt += 1
            else:
                tmp += str(cnt)+prev if cnt > 1 else prev
                cnt = 1
                prev = now
        tmp += str(cnt)+prev if cnt > 1 else prev
        if answer > len(tmp):
            answer = len(tmp)
    return answer

---

🗝️keypoint

1. 문자열의 길이가 1개이상 1000개 이하이기 때문에, 모든 경우를 확인해도 시간초과가 발생하지 않는다.
2. 1개 이상의 '일정한' 단위 이므로, aabbb가 aa3b 등으로 압축될 수 없다.