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

문제

---

https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3 

코딩테스트 연습 - 문자열 압축

 

풀이

---

입력으로 주어지는 문자열 s의 길이가 1000이고 문제 상황에 맞게 모든 압축 단위로 압축을 해보아도 시간 상 무리가 없을 것 같아 완전 탐색을 시도해보았습니다. 

 

문자열이 압축될 수 있는 모든 경우 즉, 압축 단위를 1 부터 (s의 길이 // 2) 까지 바꿔가며 전부 압축을 해보고 이전까지 구한 가장 짧은 압축 길이와 비교하여 답을 계속하여 갱신하였습니다. 이 과정에서 압축이 압축 길이만 바뀌고 같은 로직을 사용하기 때문에 따로 함수(compression)로 구현했고 메인 함수 부분인 solution에서 이를 불러왔습니다.

 

풀이 코드는 아래와 같습니다.

def solution(s):
    length = len(s)
    answer = length
    for i in range(1, length // 2 + 1):
        answer = min(answer, len(compression(i, s)))
    return answer


def compression(step, s):
    compressedStirg = ''
    nowString = s[0: step]
    repeat = 1
    # 압축 시작
    for i in range(step, len(s), step):
        nextString = s[i: i + step]
        if nowString == nextString:
            repeat += 1
        else:
            compressedStirg += str(repeat) + nowString if repeat > 1 else nowString
            nowString = nextString
            repeat = 1
    # else문에 안걸린 마지막 문자열 붙여주기
    compressedStirg += str(repeat) + nowString if repeat > 1 else nowString
    return compressedStirg