문자열 압축 (2020 카카오 신입 개발자 코딩테스트 문제)

해당 문제는 프로그래머스에서 제공된 문제입니다.

[문제 설명 및 파악]

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

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

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

먼저 문제가 요구하는 것이 무엇인지, 이를 위해 어떤 접근방식을 택해야 하는 지 파악해보자. 이 문제는 '문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘 도출'을 요구하고 있다. 그렇다면 이를 어떤 방식으로 접근하면 될까? 그냥 간단히 생각해서 1개 단위로 잘랐을 때, 2개 단위로 잘랐을 때, ... 의 길이를 구한 후 이들 중 최솟값을 반환하면 끝나는 문제이다. 그럼 이제 코드를 통해 확인하자.

---

[문제 풀이]

from collections import deque #queue사용

def string_compression(string):
    length = [] # 단위마다 자르고 압축한 문장의 길이를 저장하기 위한 리스트
    for i in range(1,len(string)//2+1): # 자를 수 있는 단위는 문장길이의 반이 최대
        queue = deque() #queue이용
        if len(string)%i == 0: # 해당 단위로 길이가 나누어떨어진다면 (떨어지지 않으면 애초에 해당 단위로 자르는 것이 불가능)
            for j in range(0,len(string),i): #슬라이싱을 통해 해당 단위로 문자들을 자르고 queue에 저장
                queue.append(string[j:j+i])
            line=[] # 자른 문자가 얼마나 연속적으로 얼마나 중복되는지 확인하기 위한 리스트
            cnt = 1 # 중복 횟수
            while queue: #자른 문자를 모두 탐색
                temp = queue.popleft()
                if len(line) == 0: #탐색의 시작
                    line.append([temp,cnt]) #일단 해당 값을 추가
                # 여기서부터 연속적 중복 체크
                elif line[-1][0] == temp: # 이어지는 문자가 이전과 중복이라면
                    cnt += 1 # 중복 체크 + 1
                    line[-1][1] = cnt # 해당 값을 문자와 함께 저장
                elif line[-1][0] != temp: # 중복이 아니라면 
                    cnt = 1 # cnt값을 1로 초기화
                    line.append([temp,cnt]) #해당 값을 저장
            result = ''# 하나의 단어로 이어주기위해 result를 빈 문자열로 저장
            for w,v in line: #기존의 중복체크를 위한 리스트를 통해 결과 확인
                if v != 1: # 중복된 단어라면
                    result += str(v)+w #중복 횟수와 문자를 같이 저장
                else: # 중복된 단어가 아니라면 
                    result += w # 단어만 저장
            length.append(len(result)) # 해당 단위의 문자열 길이의 결과 값을 저장
    return min(length) # 최소 길이를 반환

---

[마무리]

이 문제는 기출치고는 높은 난이도는 아닌 것 같았다. 어떤 방식으로 접근해야 한다라는 것만 판단하면, 그 아이디어를 구현하는 데에 큰 어려움은 없을 것이라고 생각한다.