[Programmers] 문자열 압축

🔦 문제 링크


🛠 풀이

✅ 바같 for문은 압축의 길이를 결정한다.
✅ 이너 for문은 압축할 문자열을 결정한다.

따라서, 안쪽 for문에서 현재 문자열과 이전 문자열이 같은 지 확인하도록 한다.
만약 같다면 count만 증가시키고 다음 압축 문자열로 진행한다.
이전과 현재의 문자열이 다르다면 현재 문자열의 길이를 전체 길이에 추가 시켜 줌. (미리 추가해주는 개념)

  • 여기서 이전 문자열이 아닌 현재 문자열의 길이를 구하는 이유는 마지막 문자열의 길이가 유동적이기 때문이다.

그리고 count는 1의자리일수도 그 이상 일수도 있다. 따라서, len("{}".format(c))만큼을 전체 길이에 더해주도록 한다.

마지막에 count가 1이상이라면 len("{}".format(c))만큼 더해주도록 한다.

🛠 코드

  • 먼저 전체 요소 소팅 후 특정 인덱스로 소팅
import sys
def solution(s):
    length = len(s)
    answer = length
    mid = length // 2
    for i in range(1, mid + 1):
        prev = ''
        count = 1
        curr_length = 0
        for j in range(0, length, i):
            cut = s[j:j + i] # 압축 문자열
            if prev == cut:
                count += 1
            else:
                curr_length += len(cut)
                if count > 1:
                    curr_length += len("{}".format(count))
                count = 1
                prev = cut
        if count > 1:
            curr_length += len("{}".format(count))
        answer = min(answer, curr_length)
    return answer
    

🛠 생각


현재 압축 문자열을 미리 길이에 더해주는 부분이 첫번째 핵심 아이디어 중 하나였다.
두번째 핵심 아이디어는 count의 자릿수를 처리해주는 방법이였다.

좋은 웹페이지 즐겨찾기