[Level 2] 문자열 압축

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

 

def solution(s):
    len_s = len(s)
    cand = []
    
    if len_s < 3:
        return len_s

    for u in range(1, int(len_s/2)+1):
        splt_s = [s[u*i:u*(i+1)] for i in range(int(len_s/u)+1)]
        comp_s = []

        prev = splt_s.pop(0)
        cnt = 1
    
        while splt_s:
            cur = splt_s.pop(0)
        
            if cur == prev:
                cnt += 1
            
                if len(splt_s) == 0:
                    comp_s.append(str(cnt)+cur)
                
            else:
                if cnt != 1:
                    comp_s.append(str(cnt)+prev)
                
                else:
                    comp_s.append(prev)
                
                prev = cur
                cnt = 1
                
                if len(splt_s) == 0:
                    comp_s.append(cur)
                
        cand.append(len(''.join(comp_s)))
    
    return min(cand)

 

▷ 문자열의 자르는 단위는 전체 문자열의 개수의 반까지만 고려하면 된다. 반이 넘을 경우, 문자열이 2개로 나눌 수 있고, 두 단위의 글자 개수가 달라 같을 수가 없기 때문에 고려할 필요가 없다.

 

▷ 이전 시점의 문자열 단위를 나타내는 prev 변수와 현재 시점의 문자열 단위를 나타내는 cur 변수를 두었다. while 문을 돌면서, prev 변수와 cur 변수가 같아질 경우, cnt 변수에 1을 추가하여 중복된 문자열 단위의 수를 업데이트한다. 만약 다르다면, comp_s 리스트에 cnt 변수와 문자열 단위를 합친 뒤, 추가하여 압축된 문자열을 만들어 간다. 이때, cnt 변수가 1인 경우에는 문자열 단위만 추가한다. 

 

▷ 마지막 문자열 단위에 대한 경우를 if len(splt_s) == 0 문을 통해 추가하였다. 또한 문자열의 개수가 2개 이하인 경우, 압축할 수 없으므로 if len_s < 3 문을 통해 예외적인 경우를 추가하였다.

 

▶ ''.join([List]) 함수를 통해 리스트에 있는 원소를 하나의 문자열로 합칠 수 있다.