알고리즘/코딩 테스트

[카카오] 2020 신입 개발자 블라인드 채용 1차 코딩 - 문자열 압축

망나 2021. 8. 30. 22:08

그냥 무식하게 1개 단위 ~ n-1개 단위 압축 경우의 수를 모두 계산하고 그 중 가장 작은 값은 반환하는 방법으로 해결했습니다.

 

좀 더 깔끔하게 해결한 코드가 있으면 정리해서 업데이트 하겠습니다..

 

import math

def solution(s):
    if len(s) == 1:
        return 1
    elif len(set([c for c in s])) == 1:
        count = len(s)
        return len(str(count)) + 1
    else:
        answer = len(s)

        for i in range(1, len(s)):
            idx = i
            length = 0
            prev = s[:i]
            count = 1

            for j in range(math.ceil(len(s) / i) - 1):
                curr = s[idx:idx+i]

                if prev != curr:
                    if count == 1:
                        length += i
                    else:
                        length += i + len(str(count))

                    count = 1
                else:
                    count += 1
                idx += i
                prev = curr

            if count == 1:
                length += len(curr)
            else:
                length += i + len(str(count))

            answer = min(answer, length)
        
    return answer

 

문제 풀이 및 해설 (Kakao Tech 블로그)

 

 

1 2