[프로그래머스] 문자열 압축, python

 

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

 

정확히 분류를 어떻게 해야할 지 모르겠는데, 특정 알고리즘을 사용해야 하는 느낌은 없었기에 구현 문제라고 생각이듭니다. 간략히 문제를 설명해보겠습니다.

 

1. "aabbaccc"의 문자열을 같은 문자 기준으로 "2a2ba3c"와 같이 압축할 수 있습니다. 하지만 "abcabcdede"와 같은 문자열은 하나도 압축이 불가능합니다.
2. 위와 같은 문제점 때문에 하나 단위가 아닌 여러 개의 문자를 합쳐서 압축하는 방법을 사용해봅니다. 이를테면 "abcabcdede"는 "2abccdcd"로 압축을 할 수 있습니다. 
3. 이 압축의 경우 앞에서부터 순서대로만 가능하며 압축은 한번에 한 세트( 2개씩 만 묶던가, 3개씩 만 묶던가 ... )로만 가능합니다.
4. 위와 같이 압축을 진행할 때에 가장 짧게 압죽해낸 문자열의 길이를 구해주세요.

 

아래는 코드와 풀이 입니다.

def solution(s):
    #1
    answer = 1000;
    
    #2
    if len(s) == 1:
        return 1;
        
    #3 
    for cnt in range(1, len(s)//2+1): 
        string = "";
        now = s[:cnt]; #4
        count = 0;
        
        #5
        for i in range(0, len(s), cnt):
            if s[i:cnt+i] == now: #6
                count += 1;
            else: #7
                if count < 2:
                    string += now;
                    count = 1
                else:
                    string += str(count) + now;
                    count = 1
                now = s[i:cnt+i];
        
        #8
        if count < 2:
            string += now;
            count = 1
        else:
            string += str(count) + now;
            count = 1
        
        #9
        if len(string) < answer:
            answer = len(string);
            
    return answer;

#1 - 제한사항에서 s의 최대길이는 1000이라고 주어져 있기에 처음 값은 1000으로 설정했습니다.
#2 - s의 길이가 1일 경우 압축은 상관이 없으므로 바로 1을 반환합니다.
#3 - s의 길이의 절반을 넘어서는 압축은 할 수 없으므로 for의 최대값을 len(s)//2+1로 설정한 뒤 1부터 압축을 시작합니다.
#4 - 각 문자열이 반복되는 횟수를 세기 위해서 각 문자를 먼저 담아줍니다.
#5 - 이번 압축인 cnt 만큼씩 증가하는 for문을 진행하여 now와 같은 문자가 몇번이나 반복되는지 찾아냅니다.
#6 - 만약 위에서 담아놓은 now와 다음 문자가 같다면 count를 증가시켜주고
#7 - 아닐 경우 count가 1이면 그냥 now만 count가 2이상이라면 count와 now를 문자열에 담아줍니다. 그리고 count는 다시 1로 만들어 줍니다. 그리고 now를 다음 문자로 변경해줍니다.
#8 - 문자열의 마지막 부분 문자들이 모두 같다면 string에 추가되지 않고 for문이 종료되기 때문에 직접 한번 더 해줍니다.
#9 - 이번 압축으로 생성된 문자열의 길이를 확인하고 지금까지중 최소값일 경우 answer을 갱신해줍니다.