구현_심화9) 문자열 압축

링크

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

프로그래머스

문제

"어피치"틑 문자열 압축하는 알고리즘을 공부하고 있다.

예를 들어 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않는 경우 1은 생략) 와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 한다.

 

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법이다.

 

제한사항

• s의 길이는 1 이상 1,000 이하이다.
• s는 알파벳 소문자로만 이루어져 있다.

코드

def solution(s):
    result = []
    if len(s) == 1:
        return 1
    else:
        for i in range(len(s)//2):
            rString = ''
            start = 0
            while True:
                answer = 1
                k = start
                if start >= len(s):
                    break
                string1 = s[start:start+i+1]
                while True:
                    k += i+1
                    string2 = s[k:k+i+1]
                    if string1 == string2:
                        answer += 1
                    else:
                        start = k
                        break
                if answer == 1:
                    rString += string1
                else:
                    rString += string1 + str(answer)
            result.append(len(rString))
        return min(result)