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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

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

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

출처: 프로그래머스

설명의 길이가 길어 문제 이해에 도움이 되는 일부만 발췌하였습니다. 상세한 내용은 프로그래머스 페이지에서 확인하실 수 있습니다.

---

내 기준에서 이 문제는 문제를 정확히 파악하는 것이 해결의 관건이었다.

 

처음에는 문자열 내부에 있는 중복되는 문자열로 압축했을 때 가장 짧은 길이가 나오면 되는 줄 알았다.

(ex. 'abbbccc' ➡'a3b3c')

 

하지만, 마지막 예시에 '문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.'  이라는 문구가 있는데 이를 기준으로 'abbbccc'를 다시 3개씩 자르면 'abb, bcc, c'가 되므로 자를 수 없다.

 

아래 사진은 "xababcdcdababcdcd" 를 압축하는 법에 대해 설명한다.

출처: 프로그래머스

 

이를 이해한 후 문제를 푸니 간단하게 풀렸다.

 

<정답 코드>

def solution(s):
    n = len(s)
    answer = n
    
    for i in range(1, n//2+1):
        before = s[:i]
        same = 1
        new = ''
        for j in range(i, n, i):
            temp = s[j:j+i]
            if before == temp:
                same += 1
            else:
                if same == 1:
                    new += before
                else:
                    new += str(same) + before
                
                before = temp
                same = 1
        
        if same == 1:
            new += temp
        else:
            new += str(same) + temp

        answer = min(answer, len(new))
    
    return answer

접근은 아래와 같다.

1. 문자열은 최대 len // 2 만큼 자를 수 있으므로, 1개씩 자르는 것부터 len//2개 자를 때 까지를 반복문으로 순회한다.
2. 이를 기준으로 문자열을 잘랐을 때, 반복이 되는 경우를 찾기 위해 이전 문자 값을 저장하는 before을 생성해 중복되는 문자열을 count해준다.
3. 중복되는 문자열이 있다면 count한 값을 앞에 붙여 새로운 문자열을 만든다.
4. 문자열 자르기를 탈출했을 때 마지막으로 잘린 문자열은 new에 붙지 않으므로 붙여준다.
5. answer에 더 작은 값을 업데이트 해준다.

문제 자체는 그렇게 어렵지 않았으나, 잘못 읽으면 나처럼 시간을 빼앗길 수 있으므로 신중하게 문제를 읽는 습관을 들이는 것이 좋을 것 같다.