1.6 문자열 압축

문제

반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라. 예를 들어 문자열 aabccccaaa를 압축하면 a2b1c4a3이 된다. 만약 '압축된' 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해야한다. 문자열은 대소문자 알파벳 (a-z)로만 구성되어있다.

 

접근법

1. 직관적으로 문자열의 갯수를 세어나가고 현재 문자와 다음 문자과 다를때 현재문자 + 갯수를 문자열에 붙여주면 될 것같다. 

def Solution(phrase):
    len_phrase  = len(phrase)
    char_cnt = 0
    res = ""
    for i in range(len_phrase) :
        char_cnt +=1
        if phrase[i] != phrase[i+1]:
            res += phrase[i] + str(char_cnt)
            char_cnt =0

    return res if len_phrase >= len(res) else phrase

하지만 이 접근법의 Time Complexity는  p는 원래 문자열 길이 , k는 같은 문자가 연속되는 부분 문자열의 갯수라고 했을때 O(p + k^2)가 된다. 그 이유는 문자열을 합치는 과정에서 O(n^2)의 시간이 걸리기 때문이다. 

 

StringBuilder의 과정
문자열을 이어붙일때마다 두개의 문자열을 읽어들인 뒤 문자를 하나하나 새로운 문자열에 복사해야하기 때문에 
처음에는 x, 그다음에는 2X, 그다음에는 3X...
즉 O( x+ 2x+ 3x...nx)가 되고 1+2+3+4...n = n(n+1)/2 이기 때문에 O(n^2)이 된다.

 

 

그래서 이것을 줄이기 위해서는 

문자열을 두번 읽더라도 한번 읽으면서 압축된 문자열의 길이를 먼저 계산하고 그 이후에 그 길이에 맞춰 문자열배열을 할당한 다음

압축 문자열을 차곡차곡 만들면된다. 이부분에 대한 코드를 구성해보려고 했는데 python은 배열이 동적으로 할당되어 이런식으로 구현하기가 어려웠다. 하지만 이 부분에 대한 고민을 하던 중 '  "".join(문자열 리스트) '를 알게되었다. 

 

문자열을 연결할때 += 연산은 StringBuilder와 같은 원리로 구성되어있기 때문에 time Complexity가 O(n^2)이 걸리지만, ''.join(문자열리스트)는 위의방식처럼 미리 문자열을 읽어들여 전체 길이를 계산하고 그 길이만큼 할당하여 문자열을 복사하기 때문에 문자열을 반복적으로 복사할 필요가 없어 O(N)이 걸린다. 

앞으로 python에서 문자열을 복사할때는 join을 사용해야할 것 같다. 

 

참고자료 

 https://www.bernardi.cloud/2012/11/06/python-string-concatenation-vs-list-join/

Python: string concatenation VS list join - Paolo Bernardi - Software Engineer

https://waymoot.org/home/python_string/

Efficient String Concatenation in Python