09_문자열 압축

프로그래머스

 

문자열을 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 리턴하면 되는 문제이다.

문자열 s의 길이가 1000이하고 시간 제한은 1초이므로 O(S^2)도 가능한 문제라서 완전탐색으로 풀면 된다.

 

내 풀이

s = input()


def solution(s):
    answer = 987654321
    previous = ""
    temp = 0
    check = True
    
    for i in range(1, len(s) + 1):
        index = 0
        while index < len(s) - 1:
            if previous == s[index:index+i]:
                if check:
                    temp += 1
                    check = False
            else:
                temp += i
                previous = s[index:index+i]
                check = True
            index += i

            # print(check)
        
        # temp += len(s) - index
        print(temp)
        answer = min(temp, answer)

        print(answer)
        
        
    
    return answer


solution(s)

1 ~ 문자열 길이까지의 단위로 문자열을 자른 다음에 최소 길이를 계속 갱신하는 방식으로 풀면 되겠다고 생각했다.

하지만 구현했을 때 반복되는 문자열이 처음에 나오는 경우에는 1을 더해주고, 그 이후에 반복되는 문자열이 나오는 경우에는 1을 더해주면 안된다.

예를 들어 abababccd라는 문자열이 있으면 순서대로

ab -> ab -> 길이가 2

ab -> 2ab -> 길이가 3

ab -> 3ab -> 길이가 3

이기 때문에 길이는 3으로 그대로 유지된다.

이 부분을 구현해야 하는데 계속 원하는 대로 나오지 않아서 구현에 실패했다.

그래서 풀이 코드를 봤다.

 

풀이 코드

# Q_09_문자열 압축
def solution(s):
    answer = len(s)
    # 1개 단위(step)부터 압축 단위를 늘려가며 확인
    for step in range(1, len(s) // 2 + 1):
        compressed = ""
        prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
        count = 1
        # 단위(step)만큼 증가시키며 이전 문자열과 비교
        for j in range(step, len(s), step):
            # 이전 상태와 동일하다면 압축 횟수(count) 증가
            if prev == s[j:j+step]:
                count += 1
            # 다른 문자열이 나왔다면 (더 이상 압축하지 못하는 경우라면)
            else:
                compressed += str(count) + prev if count >= 2 else prev
                prev = s[j:j+step] # 다시 상태 초기화
                count = 1

        # 남아 있는 문자열에 대해서 처리
        compressed += str(count) + prev if count >= 2 else prev
        # 만들어지는 문자열이 가장 짧은 것이 정답
        answer = min(answer, len(compressed))

    return answer

아이디어 자체는 나랑 비슷했지만 더 정확하게 구현해냈다.

그리고 나는 그냥 압축되는 문자열을 구하지 않고, 길이만 구하려고 했는데 이 풀이에서는 압축되는 문자열을 직접 만들었다.

문자열을 더해주는 부분은 다른 문자열이 나온 경우이다.

 

그리고 파이썬 리스트 슬라이싱할 때,

예를 들어 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이런 리스트가 있다고 해보자.

arr[4:24] 이런 식으로 뒷부분이 초과할 경우에는

[5, 6, 7, 8, 9, 10] 마지막까지 출력된다.