[이코테] 구현 기출문제 - 9. 문자열 압축

---

📢 '이것이 코딩 테스트다 with 파이썬' 책을 공부하고 복습하기 위해 작성했습니다.

 

2023.12.16 - [Algorithm] - [이코테] 03. 구현(Implementation)

[이코테] 03. 구현(Implementation)

---

문제

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

프로그래머스

 

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현한다.

예를 들어 "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다. 이때 N개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중에서 가장 짧은 것의 길이를 return하는 solution 함수를 완성하라.

 

제한사항

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

 

입출력 예시
s    | result
"aabbaccc" |    7
"ababcdcdababcdcd" |    9
"abcabcdede" |    8
"abcabcabcabcdededededede" |    14
"xababcdcdababcdcd"    | 17

---

문제 분석 및 알고리즘 설계

문자열을 자를 수 있는 단위는 1 ~ len(s)//2

반복문을 돌며 단위 별 길이를 비교한다.

최선의 경우, len(s) // 2 길이의 문자가 2번 반복된 것이므로, 단위를 줄이며 확인

---

나의 풀이

def solution(s):
    N = len(s)

    min_len = N
    cnt = 1
    for i in range(N // 2, 0, -1):
        c_word = ''
        # 맨 앞 자른거
        key = s[0:i]
        # print(key, end=" -> ")

        # 단위 별로 자르기
        for j in range(i, N, i):
            if len(c_word) >= min_len:
                break

            # 압축
            if key == s[j:j + i]:
                cnt += 1

            # 다른게 나오면, 이전 값 압축 표현 후 갱신
            else:
                if cnt == 1:
                    c_word += key
                else:
                    c_word += f'{cnt}{key}'
                key = s[j:j + i]
                cnt = 1

        # 마지막 잘린 거 더하기
        if cnt == 1:
            c_word += key
        else:
            c_word += f'{cnt}{key}'

        # print(c_word)
        min_len = min(min_len, len(c_word))
    return min_len


print(solution('abcabcabcabcdededededede'))

---