[프로그래머스] 문자열 압축 Python 풀이

📘 문제

플랫폼: 프로그래머스
난이도: Lv.2
유형: 그리디, 문자열

 

🔗 문제 링크

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

프로그래머스

 

데이터 처리 전문가가 되고 싶은 어피치 등장.

규칙에 따라 문자열을 압축했을 때 가장 짧은 문자열의 길이를 return 하는 문제다

규칙을 예시로 설명하자면

"aabbaccc"를 문자 1개 단위로 압축하면 "2a2ba3c"가 되고 

이때가 가장 짦은 문자열을 갖기 때문에 정답은 7이 된다.

 

 

 

🧠 접근 방법 및 풀이 과정

압축 단위를 1에서 s길이의 절반까지 고려하며 가장 짧은 문자열을 찾는 방법을 적용했다.

*문자열을 압축하려면 똑같은 규칙을 가진 문자열이 2번 이상 반복 되어야 하므로 압축 단위가 문자열 전체 길이의 절반을 넘진 않을 것이라고 판단

 

단위에 맞게 문자열을 자른 뒤 똑같은 문자가 이어진다면 이어진 갯수 + 문자열 길이,

이어지지 않고 다른 문자열이 온다면 그냥 + 문자열 길이를 해준다.

예를 들자면 

abcabcabcabcdededededede에서 길이 3을 기준으로 자르면

abc가 6번 오는데 이어진 갯수(를 문자열로 바꾼 길이)는 1, 문자열 길이는 3

ded / ede / ded / ede 이 부분은 그냥 문자열 길이인 3씩 더해줬다.

 

이렇게 문자열을 자르고 연속되게 나오는지 아닌지 판단하는걸 구현하는게 어려웠는데

itertools groupby를 사용해서 편리하게 풀 수 있었다.

 

https://docs.python.org/3/library/itertools.html#itertools.groupby

itertools — Functions creating iterators for efficient looping

 

그 과정에서 한가지 문제를 겪었는데

groupby 반복문 내부에서 실행이 2번씩 되는 것 같았다.

이 문제는 내가 해결하기 어려워서 GPT의 도움을 받았다.

 

✨ 예리한 관찰이에요! “왜 temp가 2씩 증가하는 것처럼 보일까?” 하는 의문이 생긴 거죠?

결론부터 말하면:

list(group)를 두 번 호출해서 문제가 생긴 거예요 💥

 

🔍 문제 분석

 

코드 중 이 부분을 주목해볼게요:

print(value, list(group), len(value))
count = len(list(group))  # ⛔ 여기가 문제!

여기서 group은 **이터레이터(iterator)**인데요,

list(group)을 한 번만 써도 요소가 다 꺼내지기 때문에,

두 번 호출하면 두 번째는 비어 있는 리스트가 됩니다.

 

 

❌ 현재 동작 흐름

print(value, list(group), len(value))  # 여기서 group은 소비됨
count = len(list(group))  # 이미 비어 있어서 count = 0

그래서 count == 1 조건은 성립하지 않고,

모든 경우 else로 들어가서 아래 코드가 실행되는 거예요:

temp += len(value) + len(str(count))  # count는 0이므로 len('0') == 1

즉, temp += 1 + 1 = 2가 계속 반복되는 거죠.

 

 

✅ 해결 방법

 

list(group)을 한 번만 호출하고 재사용하도록 변수에 저장하면 해결됩니다.

for value, group in groupby(s_slice):
    grouped = list(group)  # 한 번만 소비하고 저장!
    count = len(grouped)
    
    print("원래 temp", temp)
    print(value, grouped, len(value))

    if count == 1:
        temp += len(value)
    else:
        temp += len(value) + len(str(count))

 

💡 요약

문제 원인해결 방법

group을 두 번 소비함

list(group) 결과를 변수에 저장해서 재사용

 

이제 다시 실행하면 temp는 1씩 증가해서 정확히 10이 나올 거예요 😊

필요하면 깔끔하게 정리한 버전 전체 코드도 제공해드릴게요!

 

최종 코드는 아래와 같다!

 

💻 코드 & 설명

from itertools import groupby

def solution(s):
    answer = len(s)
    
    for unit in range(1, len(s) // 2 + 1):
        comp_length = 0
        s_slice = list()
        for i in range(0, len(s), unit):
            s_slice.append(s[i : i + unit])
            
        for value, group in groupby(s_slice):
            count = len(list(group))
            if count == 1:
                comp_length += len(value)
            else:
                comp_length += len(value) + len(str(count))
        
        answer = min(answer, comp_length)
        
    return answer

 

 

✨ 회고 / 느낀 점

Level 2 문제였는데 1시간이나 걸렸다..ㅠ

알고리즘을 푸는 연습이 더 필요하다고 느꼈다.

 

그리고 라이브러리를 안쓰면 좋겠지만 쓰면 편리하게 풀리는 경우가 많아서

라이브러리를 잘 알아둬야겠다!

💡 collections나 itertools 내부 라이브러리는 자주 쓰는 듯

 

 

 

💭 다른 사람의 풀이에서 어떤 분이 기가 막히게 푸셔서 깜짝 놀랐다..

나도 이런 실력자가 되어야지!!!!!!1

달린 댓글들, 궁금하면 문제 풀고 보세요!