[programmers] 문자열압축

문제 링크

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

풀이 방법

1. 몇 개 단위로 끊을지 결정. 1이 최솟값. 문자열을 반으로 나눠 앞쪽과 뒤쪽 문자열이 같은 경우가 최대로 압축한 경우이므로, len(s) // 2가 최댓값이 된다.
2. 위에서 결정된 값을 토대로 내부 for문에서 문자를 l개씩 확인한다.
3. 바로 이전의 l개 문자와 현재의 l개 문자가 같은지 확인할 것이므로 스택을 이용했다. 스택이 비어 있거나 이전의 문자와 다르면 push, 이전의 문자와 같다면 일단 pop하고 다시 stack[-1] 값을 확인해서 숫자라면 +1을, 아니라면(=1개 있다는 뜻) 2를 push한 뒤 해당 문자열을 다시 push 한다.

ex) 'aabbaccc'를 1개 단위로 끊어서 확인할 경우 스택에는 이런 식으로 저장된다
: [2, 'a', 2, 'b', 'a', 3, 'c']

코드

def solution(s):
    length = len(s)
    answer = length
    # 끊을 단위: s의 길이의 절반부터 1까지
    for l in range(length // 2, 0, -1):
        stack = []
        # 문자 l개씩 확인
        for i in range(0, length + 1, l):
            check = s[i:i + l]
            if not stack or stack[-1] != check:
                stack.append(check)
            else:
                stack.pop()
                if stack and type(stack[-1]) == int:
                    stack[-1] += 1
                else:
                    stack.append(2)
                stack.append(check)
        # 압축한 문자열
        shorter = ''.join(map(str, stack))
        # 최솟값 할당
        answer = min(answer, len(shorter))
    return answer

그런데 push/pop이 아니라 stack[-1] 값을 바로 변경하는 부분이 있어서 스택이라고 할 수 있을까? 하는 생각이 들었다. 그래서 변경해서 다시 짜본 코드는 아래와 같다.

def solution(s):
    length = len(s)
    answer = length
    for l in range(1, length // 2 + 1):
        prev = s[0:0 + l]
        cnt = 1
        tmp = ''
        for i in range(0 + l, length + 1, l):
            check = s[i:i + l]
            if prev != check:
                if cnt > 1:
                    tmp += str(cnt) + prev
                else:
                    tmp += prev
                cnt = 1
            else:
                cnt += 1
            prev = check
        # 끊어서 확인했을 때 개수가 안 맞아서 남는 것들(ex. 3개씩 끊었을 때 맨 뒤에 남는 2개)까지 더해서 최솟값 할당
        answer = min(answer, len(tmp) + length % l)
    return answer