[1주차 - Queue & Heap] 문자열 압축

본 포스팅은 프로그래머스에서 진행하는 코딩테스트와 실무역량 모두 잡는 알고리즘 스터디(Python반) 6기에 참여 하면서 공부한 내용을 정리한 것이다. (https://programmers.co.kr/learn/courses/12441)

 

 

1. [문제설명] 
2. [문제풀이] 
3. [코드리뷰를 통해 발견한 개선할 점] 
4. [리뷰완료 후 전체코드] 

 

---

[문제설명]

문자열 압축

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

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

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

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

제한사항

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

입출력 예

sresult

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

 

---

[문제풀이]

문제에 주어지는 문자열 S의 최대 길이가 1,000 이하이므로 완전탐색을 통해 풀어도 효율성 검사에 큰 문제는 없을 것으로 판단했다.

문자열의 총길이를 n이라고 할 때 문자열을 나눌 수 있는 단위의 범위는 1 ~ (n // 2 + 1)까지가 된다.

각 단위별로 부분 문자열을 만들어 비교해보고 동일한 부분 문자열이 이어서 등장하는 경우 횟수를 증가시켜 준다. 

만약 이전 부분 문자열 temp와 다른 문자열이 나타난 경우(즉, 반복되지 않은 경우)는 횟수가 2 이상인 경우에 횟수 + temp를 압축 문자열에 붙여준다. 횟수가 1 이하면 temp만 압축 문자열에 붙여준다.

문자열 길이를 벗어나지 않는 범위 안에서 문자열 압축을 진행하고, 만약 나누는 단위 미만으로 남은 문자열이 있는 경우 별다른 처리 없이 압축 문자열에 붙여준다.

위의 과정을 거쳐 만든 압축 문자열의 길이들을 heap에 넣고 처음 요소를 pop 하면 압축 문자열 중 최소 길이를 얻을 수 있다.

import heapq


def solution(s):
    if len(s) == 1:
        return 1
    heap = list()
    # 문자열을 자를 단위는 1 ~ len(S) // 2 + 1
    for dividing_len in range(1, len(s) // 2 + 1):
        compressed_string = ""
        temp = s[0:dividing_len]
        counter = 0
        for i in range(0, len(s), dividing_len):
            if temp == s[i:i + dividing_len]:
                counter += 1
            else:
                if counter == 1:
                    compressed_string += temp
                else:
                    compressed_string = compressed_string + str(counter) + temp
                temp = s[i:i + dividing_len]
                counter = 1
        else:
            if len(s) - i < dividing_len:
                compressed_string += s[i:]
            else:
                if counter == 1:
                    compressed_string += temp
                else:
                    compressed_string = compressed_string + str(counter) + temp
        heapq.heappush(heap, len(compressed_string))
    return heapq.heappop(heap)

 

 

---

[코드리뷰를 통해 발견한 개선할 점]

 

1. 변수명으로 temp는 직관적이지 않기에 사용하지 않는다.

    # 문자열을 자를 단위는 1 ~ len(S) // 2 + 1
    for dividing_len in range(1, len(s) // 2 + 1):
        compressed_string = ""
        temp = s[0:dividing_len]

변수명 temp를 부분 문자열이라는 의미의 sub_string으로 변경했다.

    for dividing_len in range(1, len(S) // 2 + 1):
        compressed_string = ""
        sub_string = S[:dividing_len]

 

 

2. 시간 복잡도를 저해하는 요소를 최소화하라.

                    compressed_string += temp
                else:
                    compressed_string = compressed_string + str(counter) + temp
        heapq.heappush(heap, len(compressed_string))

최솟값을 찾으려고 heap을 사용했는데, heap push의 시간 복잡도는 O(log N)이며 압축된 문자열의 길이를 구할 때마다 push 하도록 되어 있다. 그러나 압축된 문자열 길이를 리스트에 push( list의 append() 시간 복잡도는 O(1) )하고 min()을 사용하여 최솟값을 찾으면 시간 복잡도를 개선할 수 있다. 결론은 루프 안에서 매번 최솟값이나 최댓값을 갱신한 결과가 필요하지 않은 이상 heap을 min, max로 사용하는 것은 비효율적이다는 것이다. 해당 코드는 다음과 같이 수정하였다.

추가로 부분 문자열을 카운팅 한 결과에 따라 압축 문자열을 추가해 가는 if구분을 inline if로 변경하여 조금 더 가독성  높은 코드로 개선하였다.

                compressed_string += sub_string if counter == 1 else str(counter) + sub_string
                sub_string = S[i:i + dividing_len]
                counter = 1

        answer = min(answer, len(compressed_string))

 

 

 

3. python에서 지원하는 for, while 반복문 뒤에 else 구문은 for, while loop에서 break문이 있지 않는 이상 의미가 없다. 다시 말해 반복문을 끝까지 돌았는지 아닌지를 구분할 필요가 없다면 반복문 후에 else 문은 무의미하다. 또한 else 구문 내부의 로직이 for 구문에서 실행되는 로직과 같다면 단순히 for loop를 한 번 더 돌면 되기 때문에 else 구문은 필요 없다.

        for i in range(0, len(S), dividing_len):
            if sub_string == S[i:i + dividing_len]:
                counter += 1
            else:
                if counter == 1:
                    compressed_string += sub_string
                else:
                    compressed_string = compressed_string + str(counter) + sub_string
                sub_string = S[i:i + dividing_len]
                counter = 1
        else:
            if len(S) - i < dividing_len:
                compressed_string += S[i:]
            else:
                if counter == 1:
                    compressed_string += sub_string
                else:
                    compressed_string = compressed_string + str(counter) + sub_string

따라서 위 코드에서 for 루프를 한 번 더 돌리고 else이하를 제거하였다.

        for i in range(0, len(S) + dividing_len, dividing_len):
            if sub_string == S[i:i + dividing_len]:
                counter += 1
            else:
                compressed_string += sub_string if counter == 1 else str(counter) + sub_string
                sub_string = S[i:i + dividing_len]
                counter = 1

 

 

---

[리뷰완료 후 전체 코드]

def solution(S):
    if len(S) == 1:
        return 1

    answer = len(S)
    sub_string_lengths = list()

    for dividing_len in range(1, len(S) // 2 + 1):
        compressed_string = ""
        sub_string = S[:dividing_len]
        counter = 0
        for i in range(0, len(S) + dividing_len, dividing_len):
            if sub_string == S[i:i + dividing_len]:
                counter += 1
            else:
                compressed_string += sub_string if counter == 1 else str(counter) + sub_string
                sub_string = S[i:i + dividing_len]
                counter = 1

        answer = min(answer, len(compressed_string))

    return answer