[이코테-구현] 실전 - 09. 문자열 압축

[문제]

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

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

 

---

 

[책 풀이]

🔎 아이디어

• 1부터 문자열 절반 크기까지 step을 차례대로 증가시키면서, 각 step에 대한 압축 문자열을 구한다.
• 각 step에 대한 압축 문자열 중 가장 짧은 것이 정답이다. 

 

🔎 코드

def solution(s):
    length = len(s)
    # 반복되는게 없는 경우
    answer = length

  # 압축단위(step) : 1 ~ len(s) // 2
    for step in range(1, length//2+1):
        compressed = ""
        # 초기 압축 문자열
        prev = s[0:step]
        count = 1
        # step 만큼 증가시켜 현재 확인하는 압축 문자열과 같은지 확인
        for i in range(step, length, step):
            # 확인하는 문자열이 같다면 count 증가
            if prev == s[i:i+step]:
                count += 1
            # 다른 문자열이 나온 경우 (현재 문자열로 더이상 압축 불가)
            else:
                # s문자열 중 현재까지 확인한 문자열까지 압축된 결과
                compressed += str(count) + prev if count >= 2 else prev
                # 확인하는 압축 문자열 갱신    
                prev = s[i:i+step]
                count = 1

        # 남아 있는 문자열 더하기
        compressed += str(count) + prev if count >= 2 else prev

        # 압축 문자열이 가장 짧은 것이 정답
        answer = min(answer, len(compressed))
    
    return answer

print(solution(input()))

 

---

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬 

* 포스팅에 책의 내용과 개인적인 해석이 같이 포함됩니다.