06_문자열 압축

오늘 내가 공부했던 문제들 중에 유일하게 스스로 풀었던 문제이다!

 

 

어렵게 생각하지 않았다.

# abcabcab
#
# [a b c a b c a b ] > 8
# [ab ca bc ab] > 8
# [abc abc ab] > 6
# [abca bcab] > 8

 

혼자서 주석들을 이렇게 써보고 문자열들을 이렇게 나눈다음에 각각을 리스트에 넣고, 인덱스를 사용하여

현재 인덱스가 지칭하는 항목과 그 다음항목이 같다면 ''으로 치환해주어 겹치는 부분을 사라지게 했다. 그 과정에서 숫자를 넣을 부분이 있어야 하기 때문에, overlap_lst란 개념을 도입해서 겹쳐져있는 문자들을 합쳐서 그 숫자를 세어주었다.

 

문제에서 문자열로 반환이 아닌, 가장짧은 길이만 반환하면 되기에 생각가능한 방법이었다.

input = "abcabcabcabcdededededede"


def string_compression(string):
    lst = []
    min_string = len(string)
    for i in range(1,len(string)):
        for j in range(0,len(string),i):
            lst.append(string[j:j+i])


        overlap_lst = []
        for k in range(len(lst)-1):

            if lst[k] == lst[k+1]:
                overlap_lst.append(lst[k])
                lst[k] = ''


        lst = ''.join(lst)
        
        if min_string>(len(lst) + len(list(set(overlap_lst)))):
            min_string = (len(lst) + len(list(set(overlap_lst))))

        lst =[]

    return min_string


print(string_compression(input))  # 14 가 출력되어야 합니다!



# abcabcab
#
# [a b c a b c a b ] > 8
# [ab ca bc ab]      > 8
# [abc abc ab]       > 6
# [abca bcab]        > 8
# seq[i:i+length] for i in range(0, len(seq), length)

간단한데 생각보다 어려웠다