[프로그래머스]Lv2. 문자열 압축(Python)

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

프로그래머스

 

문제 접근

 

이전에 답을 보고 작성했지만 직접 손으로 써보지 않아 애매하게 이해하고 끝낸 문항.. 이번엔 제대로 끝내자!!

 

문제..!!

1. 사실 문자열을 자르는 범위가 1부터 시작인 건 쉽게 알 수 있지만 최대를 구하는 것이 문제였다. 

2. aaabbb를 생각하면 1개 단위로 자르면 3a3b(=4), 3개 단위로 자르면  aaabbb(=6)이므로 큰 단위로 압축한다고 해서 더 짧은 문자열은 아니다... 다 구해봐야 하는 듯

 

이 문제에서 코드 작성에 있어서 핵심은 

1. 첫 번째 껍데기의 반복문을 압축 단위를 늘려가는 걸 기준으로 하는 것 그리고 그 범위를 지정하는 것

2. 내부의 반복문에서 만약 이전 문자와 다른 문자가 튀어나오는 경우 새로운 하나의 문자로 재설정하고 카운트 횟수를 리셋하는 것

 

시간 복잡도의 경우 문자열의 길이가 1000 이하로 정해 있으므로 O(N^2)까지 가능하다.

 

코드

def solution(s):
    answer = len(s)

    for step in range(1, len(s)//2+1):  # 압축 단위는 1 ~ n/2까지 가능, 압축 단위를 기준으로 반복문(핵심1)
        compressed = ""	# 문자열을 계속 저장해나갈 변수 
        prev = s[0:step]	# 비교할 문자 저장 
        cnt = 1 # 압축 횟수를 세기 위한 변수

        for j in range(step, len(s), step): # step(단위)만큼 증가시키며 이전 문자열과 비교
            if prev == s[j:j + step]:
                cnt += 1
            else:
                if cnt >= 2:
                    compressed += str(cnt) + prev  # 반복 횟수(cnt)와 문자열(prev)을 합쳐서 압축된 문자열 추가
                else:
                    compressed += prev  # 반복 횟수가 1인 경우, 원래 문자열(prev)을 그대로 추가
                prev = s[j:j + step]	# 새로운 하나의 문자로 재설정(핵심2)
                cnt = 1	# 카운트 횟수 리셋 
        
        compressed += str(cnt) + prev if cnt >= 2 else prev
        
        answer = min(answer, len(compressed))	# 이전 압축 문자열의 길이와 비교해서 더 작은 값으로 갱신 
        
    return answer