문제

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

요약

  • 문자열이 주어지면, 1개 이상의 단위로 잘라서 압축한다.
  • 압축했을 때, 가장 짧은 문자열의 길이를 반환한다.


분류

  • 문자열

풀이

1. 내 풀이

  • 그냥 직관적인 풀이다.
  • 2차원 리스트들 이용했다.
  • 단위의 범위는 1 ~ 문자열의 길이 // 2 로 한다. 문자열의 길이 // 2 보다 긴 길이로는 압축될 수 없다.
  • [개수, 문자열] 의 형식으로 answer 배열의 첫 요소 넣는다. 다음 arr 의 요소와 비교해서 문자열이 같으면 +1 (* 이면 2)
  • 마지막에 리스트를 1차원으로 풀고, * 없애고, join 으로 문자열 만들고, 최단 길이 갱신.


import sys


def solution(s):
    min_len = sys.maxsize if len(s) != 1 else 1
    key = len(s) // 2 # 문자열 길이 // 2 보다 긴 길이로는 압축될 수 없다.

    for length in range(1, key + 1): #단위 선택 (1 ~ 문자열 길이//2)

        arr = [s[i:i+length] for i in range(0, len(s), length)] #문자열 잘라서 list 로
        answer = [['*', arr[0]]]

        for j in range(1, len(arr)):
            if answer[-1][1] == arr[j]: #answer 의 마지막 문자와 arr의 문자가 같으면 앞의 수 +1
                answer[-1][0] = 2 if answer[-1][0] == '*' else answer[-1][0] + 1
            else: #다르면 append
                answer.append(['*', arr[j]])

        answer_str = ''.join([str(word) for words in answer for word in words]) #join 으로 한 문자열로 합침 (2차원 리스트 flatten)
        answer_str = answer_str.replace('*', '') # * 모두 지우기
        min_len = min(min_len, len(answer_str)) # 최단 길이 갱신

    return min_len

2. 최적화 풀이

  • <취업과 이직을 위한 프로그래머스 코딩테스트 문제 풀이 전략> 을 참고한 코드입니다. (링크)
  • 실제 압축된 배열을 만들지 않더라도 길이만 재면 된다는 점에 집중했다.
  • comp 에 저장된 문자열과 temp 에 저장된 문자열의 비교를 중심으로 압축된 길이를 구한다.
def solution(s):
    answer = len(s)
    for x in range(1, len(s) // 2 + 1):
        comp_len = 0
        comp = ''
        cnt = 1
        for i in range(0, len(s) + 1, x):
            temp = s[i:i+x]
            if comp == temp: cnt += 1
            elif comp != temp:
                comp_len += len(temp)
                if cnt > 1: comp_len += len(str(cnt))
                cnt = 1
                comp = temp
        answer = min(answer, comp_len)

    return answer