[이것이 코딩 테스트다 with Python] Chapter 12. 구현 - 문자열 압축

< 문자열 압축 >

 

💬 문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다.최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
....

 

입력	출력
"aabbaccc"   "ababcdcdababcdcd"   "abcabcdede"   "abcabcabcabcdededededede"   "xababcdcdababcdcd"	7   9   8   14   17

💬 입력 조건

• s ( 1 ≤ s ≤ 1,000 )
• s는 알파벳 소문자로만 이루어져 있다.

---

✍ 문제요약

s라는 변수가 주어지는데, "aabbaccc" 이런값을 가진다. s의 내부 문자중에 연속적으로 반복되는 부분을 숫자로 표현해서 s의 전체길이를 줄여서 최소의 길이를 가지는 값을 구해야한다. 이 때 문자의 자릿수는 1자리 이상이 될 수도 있다. 만약 문자의 1자릿수로 반복되는 문자를 줄인다면 "2a2ba3c" 이렇게 표현할 수 있다. 만약 2자릿수로 본다면 "aa bb ac cc" 이렇게 잘라서 반복 구간을 살펴볼 수 있는데, 현재 예시에서는 반복되는 문자가 없다. 

💯 문제링크

프로그래머스의 "문자열 압축"와 동일한 문제이다.

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

프로그래머스

---

✅  문제 풀이

• 문제에서 알려준 것 처럼 실제로 압축된 문자를 만드는 방법을 택했다.
• 문자를 압축할 수 있는 자릿수는 1자리 부터 s의 절반 자리 수 만큼이다. s의 길이의 절반 이상으로 자르면 반복된 문자가 나올 수 없기 때문이다. 
• 기준이 되는 문자와 비교하여 몇개가 동일한지 수를 파악하여 실제로 문자를 압축한다.

def solution(s):
    s_len = len(s)
    Min = s_len
    for cut in range(1,s_len // 2 + 1):    # 1 ~ s길이의 절반 ( 압축 시키는 자릿 수 )
        compressed = ""                    # 압축시킨 문자를 담을공간
        prev_str = s[0 : cut]              # 기준이 되는 문자
        count = 1                          # 반복 수
        for i in range(cut,s_len,cut):     # cut 단위로 for문 반복
            if prev_str == s[i : i + cut]: # 반복이면 count + 1
                count += 1
            else:                          # 반복이 끊기면 문자 압축
                compressed += str(count) + prev_str if count >= 2 else prev_str
                prev_str = s[i : i + cut]
                count = 1
        
        # 남아 있는 문자열 까지 compressed에 추가
        compressed += str(count) + prev_str if count >= 2 else prev_str
        Min = min(Min,len(compressed))
        
    return Min