프로그래머스 - 문자열 압축 [파이썬]

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

코딩테스트 연습 - 문자열 압축

---

풀이 과정

문자열을 몇개 단위로 잘라서 압축해야 가장 짧은 압축 문자열이 되는지 고려하면서 그때의 압축 문자열의 길이를 구하는 문제이다.

 

aaaabbbb는 4a4b, 2a2a2b2b, aaaabbbb가 가능하다. 높은 숫자 단위로 압축해야 가장 짧은 문자열이 될까?

 

aaaabbbbaaaabbbb는 8개 단위로 자르면 2aaaabbbb이고 4개 단위로 자르면 4a4b4a4b이다. 4개 단위로 잘랐을때 압축 문자열이 더 짧다. 몇 개로 잘라야 가장 짧은 압축 문자열이 되는지는 미리 알 수 없고 다 구해봐야 알 수가 있다.

 

k개 단위로 자른다고 할 때, 1 ~ len(문자열) // 2 + 1 범위로 일일이 잘라서 문자열을 만들어서 답을 구할 수 있다.

 

k가 전체 문자열의 길이의 반을 넘을 수는 없다. 넘으면 압축이 되는 경우가 전혀 없기 때문이다

---

소스 코드

def string_cut(string, cut):
    string_list = []
    number = 1
    real_string = ""
    length = len(string)
    string_list = [string[i:i+cut] for i in range(0, len(string), cut)]
    list_length = len(string_list)
    
    for i in range(1, list_length):
        if string_list[i-1] == string_list[i]:
            number += 1
        else:
            if number == 1:
                real_string += string_list[i-1]
            else:
                real_string += str(number)
                real_string += string_list[i-1]
            number = 1
    
    if string_list[list_length-2] == string_list[list_length-1]:
        real_string += str(number)
        real_string += string_list[list_length-1]
    else:
        real_string += string_list[list_length-1]
    
    return len(real_string)
    


def solution(s):
    answer = 12345678
    if len(s) == 1:
        return 1
    for i in range(1, len(s) // 2 + 1):
        temp = string_cut(s, i)
        if answer > temp:
            answer = temp
    return answer