문자열 압축 - 2020 카카오 공채 (python)

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 문자열 압축 LV2

https://programmers.co.kr/learn/courses/30/lessons/60057
모든 숫자 단위로 쪼개보고 가장 짧은 값을 찾는 완전탐색
압축하는 과정에서 스택을 사용할 수 있음

👀 깃헙 소스

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

입출력 예
['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c']
2a2ba3c ===> 7
문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

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

s				result
--------------------------------------
"aabbaccc"			7
"ababcdcdababcdcd"		9
"abcabcdede"			8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"		17

솔루션
s 길이가 그렇게 크지 않으므로 1부터 모든 단위로 쪼개서 확인해본다.
각 단위로 쪼갠 압축 문자열을 compressed를 통해 cand에 저장하고
최소값을 꺼낸다

코드

풀이 1. "count" 전역으로 해서 사용

# 파이썬
def solution(s):
    LENGTH = len(s)
    cand = [LENGTH]  # 1~len까지 압축했을때 길이 값

    for size in range(1, LENGTH):
        compressed = ""
        # string 갯수 단위로 쪼개기 *
        splited = [s[i:i+size] for i in range(0, LENGTH, size)]
        count = 1

        for j in range(1, len(splited)):
            prev, cur = splited[j-1], splited[j]
            if prev == cur:  # 이전 문자와 동일하다면
                count += 1
            else:  # 이전 문자와 다르다면
                compressed += (str(count) + prev) if count > 1 else prev
                count = 1  # 초기화

        compressed += (str(count) + splited[-1]) if count > 1 else splited[-1]
        cand.append(len(compressed))

    return min(cand)  # 최솟값 리턴

풀이 2. stack 사용

-> 참고 :
유사문제 "짝지어 제거하기" https://programmers.co.kr/learn/courses/30/lessons/12973

# 파이썬
def solution(s):
    LENGTH = len(s)
    STR, COUNT = 0, 1
    cand = [LENGTH]  # 1~len까지 압축했을때 길이 값

    for size in range(1, LENGTH):
        compressed = ""
        # string 갯수 단위로 쪼개기 *
        splited = [s[i:i+size] for i in range(0, LENGTH, size)]
        stack = [[splited[0], 1]]

        for unit in splited[1:]:
            if stack[-1][STR] != unit:  # 이전 문자와 다르다면
                stack.append([unit, 1])
            else:  # 이전 문자와 다르다면
                stack[-1][COUNT] += 1

        compressed += ('').join([str(cnt) + w if cnt > 1 else w for w, cnt in stack])
        cand.append(len(compressed))

    return min(cand)  # 최솟값 리턴

*splited
    ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] 
    ['aa', 'bb', 'ac', 'cc']
    ['aab', 'bac', 'cc']
    ['aabb', 'accc']
    ['aabba', 'ccc']
    ['aabbac', 'cc']
    ['aabbacc', 'c']

참고문제 :
가장 긴 팰린드롬 - 단위쪼개서 확인하는 흐름 유사
https://programmers.co.kr/learn/courses/30/lessons/12904