[카카오 코테 2020 | python] 문자열 압축 ✅

• 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60057
• 문자열 압축 문제, 구현/시뮬레이션
• Level2

 

Q1) 문제를 어떻게 이해했나요?
A1)

Q2) 문제를 어떻게 풀 예정인가요?
A2)

 

🔥 내 풀이

• 문자열을 슬라이싱 후 미리 리스트로 저장해놓고 반복함.
• list_compressed 전체가 메모리에 올라가므로 공간 사용 ↑
• 슬라이싱 연산이 반복되므로 시간도 조금 더 듦
• 리스트로 저장하고 다시 비교 → 속도 느림
• s[-(len(s)%i):] 추가 처리 → 로직 복잡도 ↑
• 시간복잡도 → O(n²)

def solution(s):
    best_compressed = 1001
    i = 1
    while i <= len(s)//2+1:
        compressed = []
        list_compressed = [s[x-i:x]for x in range(i, len(s)+1, i)]
        before_count = 1
        compared = list_compressed[0]
        
        for com in list_compressed[1:]:
            if compared == com: # 동일하면 다음으로 넘어감
                before_count += 1
            else: # 그렇지 않으면 compressed에 저장
                if before_count == 1:
                    compressed.append(compared)
                else:
                    compressed.append(str(before_count) + compared)
                    before_count = 1
                compared = com
        if before_count != 1:
            compressed.append(str(before_count) + compared)
        else:
            compressed.append(compared)
        if len(s)%i != 0:
            compressed.append(s[-(len(s)%i):])
        if best_compressed > len("".join(compressed)):
            best_compressed = len("".join(compressed))
        i+=1
    return best_compressed

 

🤖 최적화된 코드

• 리스트 슬라이싱 없이 바로 순회하면서 비교
• 매번 필요한 부분만 슬라이싱
• 시간복잡도 → O(n²)

def solution(s):
    n = len(s)
    if n == 1:
        return 1

    min_length = n  # 압축 전 길이로 초기화

    for size in range(1, n // 2 + 1):
        compressed = []
        prev = s[0:size]
        count = 1

        for i in range(size, n, size):
            cur = s[i:i+size]
            if cur == prev:
                count += 1
            else:
                if count > 1:
                    compressed.append(str(count))
                compressed.append(prev)
                prev = cur
                count = 1

        if count > 1:
            compressed.append(str(count))
        compressed.append(prev)

        compressed_len = sum(len(chunk) for chunk in compressed)
        min_length = min(min_length, compressed_len)
        
    return min_length