카카오 코딩테스트- 문자열 압축, 파이썬

1. 문제 

문자열을 압축하여 표현할 때 가장 짧은 문자열 수를 구하라 

 

2. 풀이

1부터 문자열 길이의 절반까지 반복해서 압축된 문자열의 길이 중 최소값을 구하는 식으로 풀었다. 

Brute force 문제인데 왜 함수명을 dfs라쓴지는 모르겠다. 1번문제 답게 어렵지 않게 풀 수 있다. 

 

다만 두 가지 때문에 테스트케이스를 틀렸는데 

 

1) 아래처럼 범위를 돌리다보니까 s 길이가 1인 경우 for문이 실행되지 않아 ret 배열이 비어버려 오류가 난다. 

    for i in range(1, len(s)//2 + 1) :
        dfs(s, i, ret)

그냥 구현만 하려고 위에 문자열 길이가 1인 경우 예외처리를 해줬는데 주의해야할 부분이다 

 

2) 반복되는 문자열이 나온 경우 앞의 숫자 예를들어 aaa의 경우 3a로 생각하고 숫자 하나만 카운트해줬는데 문자열 반복이 10이 넘어갈 경우 문제가 생긴다. 10a의 길이는 3이기 때문이다. 따라서 temp를 급하게 추가해서 해결했는데 문제에서 요구하는 문자열을 구하지 않고 길이만 체크하는 꼼수를 쓴 결과이다. 

def solution(s):
    if len(s) == 1 :
        return 1
    ret = []
    for i in range(1, len(s)//2 + 1) :
        dfs(s, i, ret)
    return min(ret)
    
def dfs(s, idx, ret) :
    arr = []
    for i in range(0, len(s), idx) :
        arr.append(s[i: i+idx])
    j = 1
    cnt = len(arr[0])
    prev = arr[0]
    while j < len(arr) :
        if prev == arr[j] :
            temp = 1
            while j < len(arr) and prev == arr[j] :
                j += 1
                temp += 1
            cnt += len(str(temp))
        else :
            prev = arr[j]
            cnt += len(arr[j])
            j += 1
    ret.append(cnt)

3. 개선

만약 실제 시험이었다면 테스트케이스가 틀려 당황했을듯 싶다. 문제에서 요구한 대로 구현하고 예외를 고려하자. 

C하다 파이썬으로 넘어와서 코드가 파이썬같지 않다.