문제 링크

개요

  • 문자열 처리 능력이 요구되는 문제다.

문제 조건

  • 문자열에서 반복되는 문자 또는 단어를 압축하고 가장 짧게 압축된 길이를 반환한다.

문제 해설

  • 문자열을 단일 문자부터 2등분이 될 때까지 한 단위씩 늘려가면서 분리된 문자들에 대한 압축 과정을 진행한다.
  • 분리된 문자들을 순회하면서 반복되는 문자열을 무시하고 남은 문자열의 길이를 세는 방법도 있지만,
    여기선 문자열을 형식에 맞게 압축시키고 그 길이를 구한다.
  • 이전 문자열이 담길 메모리와 해당 문자열이 반복된 횟수를 기록하는 변수를 각각 선언한다.
  • 분리된 문자들을 순회하면서 현재 문자와 메모리가 다르면(반복되지 않으면)
    압축된 문자열에 메모리를 추가하고 초기화한다.
  • 모든 과정에 대한 최소 길이 값을 기록하고 반환한다.

해설 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

    for unit in range(1,len(s)//2+1):
        s_range = list(range(0, len(s), unit))+[None]
        s_split = [s[s_range[i]:s_range[i+1]] for i in range(len(s_range)-1)]+['']
        new_s, memory, cnt = str(), s_split[0], 1
        for s_unit in s_split[1:]:
            if memory != s_unit:
                new_s += ((str(cnt) if cnt > 1 else str()) + memory)
                memory, cnt = s_unit, 1
            else:
                cnt += 1
        answer = min(answer, len(new_s))

    return answer