[프로그래머스] 문자열 압축 (2020 KAKAO BLIND) / python

1. 문제 설명

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

문자열에서 같은 값이 연속해서 나타나는 것을
그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.

간단한 예로 "aabbaccc"의 경우
"2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데,
이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다.
예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다.
문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

압축할 문자열 s가 매개변수로 주어질 때,
위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록
solution 함수를 완성해주세요.

 

2. 풀이 전 계획과 생각

s의 길이는 1이상 1000 이하이다.

먼저, 완전 탐색으로 접근해보자.

1 ~ 500만큼 문자열을 잘라보고 여기서 가장 짧은 문자열을 구하면 된다.

시간 복잡도가 O(500 * 500)이므로 완탐이 가능하다.

1. 문자열의 길이를 잘라주자. (1~500만큼)
2. 그리고 그때마다, 문자 시작부터 끝까지 단위로 잘라주고 기준과 비교해주자.
   • 같으면, count += 1
   • 다르면,
     • result에 count + temp 추가해준다. (단, count가 1이면 temp만 추가해준다.)
     • 기준은 해당 잘라진 문자열로 초기화, count는 1로 초기화 해준다.

 

3. 풀이

def solution(s):
    answer = 1000
    N = len(s)
    
    for unit in range(1, N // 2 + 1):
        result = ""
        temp = s[:unit]
        count = 1
        
        for idx in range(unit, N, unit):
            if temp == s[idx:idx + unit]:
                count += 1
            else:
                if count == 1:
                    result += temp
                else:
                    result = result + str(count) + temp
                temp = s[idx:idx + unit]
                count = 1
        
        answer = min(answer, len(result))
    
    return answer

문제점

마지막 temp에 담은 변수를 result에 추가해주지 않았다.

 

4. 2차 풀이

def solution(s):
    answer = 1000
    N = len(s)
    
    for unit in range(1, N // 2 + 1):
        result = ""
        temp = s[:unit]
        count = 1
        
        for idx in range(unit, N, unit):
            if temp == s[idx:idx + unit]:
                count += 1
            else:
                if count == 1:
                    result += temp
                else:
                    result = result + str(count) + temp
                temp = s[idx:idx + unit]
                count = 1
        
        if count == 1:
            result += temp
        else:
            result = result + str(count) + temp
        
        answer = min(answer, len(result))
    
    return answer

 

5. 풀이하면서 막혔던 점과 고민

테스트 케이스 1개가 통과하지 않는다.

입력 조건이 1개인 경우

→ slicing 해주는 반복문에 들어가지 않는다. 그러므로, 따로 처리해주자.

 

6. 3차 풀이

def solution(s):
    answer = 1000
    N = len(s)
    
    if N == 1:
        return 1
    
    for unit in range(1, N // 2 + 1):
        result = ""
        temp = s[:unit]
        count = 1
        
        for idx in range(unit, N, unit):
            if temp == s[idx:idx + unit]:
                count += 1
            else:
                if count == 1:
                    result += temp
                else:
                    result = result + str(count) + temp
                temp = s[idx:idx + unit]
                count = 1
        
        if count == 1:
            result += temp
        else:
            result = result + str(count) + temp
        
        answer = min(answer, len(result))
    
    return answer

 

7. 풀이 후 알게된 개념과 소감

• 입력 조건이 1개일 때처럼 조건이 제일 작은 것과 제일 큰 경우까지의 케이스를 확인해주자.
• 문자열 슬라이싱을 활용하자.