문제
문자열을 압축할 때 가장 짧게 표현할 수 있는 방법
ex) abcabcdede : 3개씩 압축하면 2abcdede
문자열 s의 길이는 1 이상 1,000 이하
s는 알파벳 소문자로만 이루어져 있음
입출력 예시
| s | result |
|---|---|
| “aabbaccc” | 7 |
| “ababcdcdababcdcd” | 9 |
| “abcabcdede” | 8 |
| “abcabcabcabcdededededede” | 14 |
| “xababcdcdababcdcd” | 17 |
접근
1 ~ n/2 개씩 압축하는 모든 방법을 비교하여 가장 짧은 경우를 찾는다.
마지막에 포문을 나와서 한번더 담아주는 과정을 거쳐야 한다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def solution(s):
minSize = 9999
if len(s) == 1:
return 1
for size in range(1, len(s) // 2 + 1):
result = ""
substr = s[:size]
cnt = 1
for i in range(size, len(s), size):
if s[i:i+size] == substr:
cnt += 1
else:
if cnt == 1:
cnt = ""
result += str(cnt) + substr
substr = s[i:i+size]
cnt = 1
if cnt == 1:
cnt = ""
result += str(cnt) + substr
if len(result) < minSize:
minSize = len(result)
return minSize