문제 링크

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

문제 설명

• 문자열을 1개, 2개, ... N개 단위로 잘라 압축
• 반복 횟수 + 반복되는 문자열 형태
• 반복 횟수가 1일 경우 횟수 생략
• 압축된 문자열의 길이의 최솟값 리턴

풀이

• 1개, 2개, ... N // 2개로 잘라 압축한 경우 각각 카운트
  • N이 최대 1000이기 때문에 O(N**2) 가능
• 자르는 개수를 step이라 할 때
• 원소가 step개 들어있는 i번째 큐, i+1번째 큐 비교하며 압축
• 1을 제거할 때 10, 100, ... 제거하지 않도록 주의

코드

from collections import deque


def solution(s):
    min_len = len(s)
    for step in range(1, len(s) // 2 + 1):
        min_len = min(min_len, get_len(s, step))
    return min_len


def get_len(s, step):
    before = deque(s)
    after = deque()

    # i번째 큐
    prev = deque()
    for _ in range(step):
        prev.append(before.popleft())

    # i번째 큐, i+1번째 큐 비교
    count = 1
    while len(before) >= step:
        # i+1번째 큐
        curr = deque()
        for _ in range(step):
            curr.append(before.popleft())
        # 비교
        if prev == curr:
            count += 1
        else:
            after.append(str(count))
            for _ in range(step):
                after.append(prev.popleft())
            prev = curr
            count = 1

    # 마지막 남은 큐
    after.append(str(count))
    for _ in range(step):
        after.append(prev.popleft())
    while before:
        after.append(before.popleft())

    # 1 제거
    compressed = ''.join([s for s in after if s != '1'])
    return len(compressed)