문제

링크

복습 요망!!

풀이

풀이 방법은 구하기 쉬웠으나 구현에서 시간이 오래 걸린 문제이다. 손으로 풀라면 풀겠는데 코드로 구현하자니 어려웠다...)

제가 생각한 풀이 방법은 아래와 같다.

1. 문자 탐색단위 지정 (1개, 2개, 3개, ...)

2. 문자열 탐색 시 탐색단위가
   바로 뒤의 문자열 단위가 같으면 압축
   바로 뒤의 문자열 단위가 다르다면 문자열 탐색단위를 바로 뒤의 문자열 단위로 update

3. 탐색단위를 하나씩 늘려가면서 이러한 과정을 반복 수행

풀이 방법을 떠올리는 것은 굉장히 쉬울 것이다. 코드로 내 생각을 옮길 때 천천히 꼼꼼하게 코딩하는 연습을 하자.

코드

# 내 풀이
def solution(s):
    answer = len(s)

    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step]
        count = 1

        for j in range(step, len(s), step):
            if prev == s[j:step + j]:
                count += 1
            else:
                compressed += str(count) + prev if count > 1 else prev
                prev = s[j:step + j]
                count = 1

        compressed += str(count) + prev if count > 1 else prev
        answer = min(answer, len(compressed))

    return answer



# 다른 사람의 풀이
def solution(s):
    length = len(s)
    cand = [length]

    for size in range(1, length):
        compressed = ""
        splited = [s[i:i+size] for i in range(0, length, size)]
        count = 1

        for j in range(1, len(splited)):
            prev, cur = splited[j-1], splited[j]
            if prev == cur:
                count += 1
            else:
                compressed += (str(count) + prev) if count > 1 else prev
                count = 1

        compressed += (str(count) + splited[-1]) if count > 1 else splited[-1]
        cand.append(len(compressed))

    return min(cand)