[Programmers 파이썬] 문자열 압축

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

 

카카오 2020 공개채용 문제이다.

 

특별히 사용한건 없고, 우선 나는 새로운 배열에 문자열을 부분부분 나눠서 저장해주고 시작했다.

처음에는 그냥 새로운 문자열을 만들어주기보단, 만들어질 문자열의 길이를 미리 예측하여 더해주려고 했으나,

aaaaaaaaaa -> 10a result 3 

a -> result 1

등의 예외 처리해줄 것이 너무 많아 이내 새로운 문자열을 그냥 만드는 것으로 방향을 틀었다.

 

def solution(s):
    answer = len(s)
    str_len = 1
    
    while str_len <= len(s)//2:
        temp = 0
        li = []
        
        new_str = ""
        
        while temp < len(s):
            li.append(s[temp:temp+str_len])
            temp += str_len
            
        cont = 0
            
        for i in range(0,len(li)-1):
            
            if li[i] == li[i+1]:
                cont += 1
                if i == len(li)-2:
                    new_str = new_str + str(cont+1) + li[i]
            else:
                if cont == 0:
                    new_str += li[i]
                else:
                    new_str = new_str + str(cont+1) + li[i]

                if i == len(li)-2:
                    new_str += li[i+1]
                cont = 0
         

        answer = min(answer,len(new_str))

        str_len += 1
    
    return answer

print(solution("aaaaaaaaaa"))

 

cont변수를 통해서 문자열이 몇번이나 반복되었는지 셀 수 있었고, 쭉 탐색하다가 다른 문자열을 만났을 때,cont 변수를 사용해서 새로운 문자열에 더해주었다.

 

예외 처리 하나는 이렇게 쭉 진행했을 때,

aaaaabbbbb -> 5a5b가 나와야하는데, 5b는 생략되어 버린다.

이를 해결하기 위해 맨 마지막까지 탐색하였을땐, 연속되고 있었을때 아닐때를 구분지어서 새로운 문자열에 더해준 것을 볼 수 있다.

 

구현은 역시 풀면 풀수록 느는것 같다😎