프로그래머스 문자열 압축 파이썬

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/60057

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

 

 

문제

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

 

입출력

입출력 예

s / result

"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이 됩니다.

 

문제 풀이를 위해 생각한 것

1. 자르는 단위는 최대 무엇이 되어야 할까?
   1. 1부터 문자열 길이의 절반까지 단위를 올린다.
   2. 문자열은 앞에서부터 정해진 숫자만큼 자를 수 있기에, 절반 이상의 단위는 고려하지 않아도 된다.
2. 원소비교는 어떤 방식으로 해야 하는가?
   
   1. 단위만큼 cur 변수에 문자를 할당했다.
   2. 이후 리스트의 첫번째 원소를 단위만큼 pop하고, 이를 _next변수에 할당했다.
   3. 리스트에 단위 이하의 원소가 남았으면 이를 압축하지 못하고 그저 새로운 문자열에 더해줘야 하기에, 남아있는 원소를 모두 pop 해 _next에 할당했다.
   4. 원소가 아예 없으면 _next 값을 ''으로 초기화 하여 종료 조건을 설정했다.
   5. prev, cur, _next를 비교하여 둘 중 하나라도 같으면 연속되는 원소로 samePool 리스트에 추가했고, 해당 원소와 다른 원소가 _next일 때(더 이상 연속되지 않을 때) 같은 원소를 모두 압축했다.
   6. while문의 마지막에는 prev = cur, cur = next로 설정하여 다음 반복문에서 _next변수만을 초기화 해 비교할 수 있도록 했다.

 

사용한 자료구조 / 알고리즘

배열 / 구현

 

풀이 코드

def solution(s):
    
    result = []
    if len(s) == 1:
        return 1
    # 문자열 구분 단위: i
    for i in range(1, (len(s) // 2) + 1): # 1부터 s의 길이 // 2 단위 동안
        
        listWord = list(s)
        
        # 초기화
        newStr = ''
        prev = ''
        cur = ''
        samePool = []
        sameLetter = ''
        
        for j in range(i): # 초기값
            cur += listWord.pop(0)
        
        while True:
            _next = ''
            if cur == '': # 종료조건
                result.append(len(newStr))
                break
            
            if len(listWord) >= i: # listWord에 있는 원소가 단위보다 많거나 같으면
                for k in range(i):
                    _next += listWord.pop(0)
            elif len(listWord) < i and listWord: # 단위보다 작지만 원소는 있을 때
                while listWord:
                    _next += listWord.pop(0)
            elif not listWord: # listWord에 원소가 없으면
                _next = ''
            
            if prev == cur or cur == _next: # 연속되는 원소
                samePool.append(cur)
                sameLetter = cur
            else:
                newStr += cur
            
            if samePool and cur != _next: # 연속되는 원소 끝, 압축
                cnt = samePool.count(sameLetter)
                newStr += str(cnt) + sameLetter
                samePool = []
                sameLetter = ''
                
            # 다음으로 이동
            prev = cur
            cur = _next
    return min(result)

 

문제에서 중요한 부분

원소를 얼만큼의 단위까지 자를 것인가, 원소를 압축하는 방법은 무엇인가?