[프로그래머스 Programmers][Python] 문자열 압축

문제 : https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축 | 프로그래머스

 

이 문제는 코딩 인터뷰 완전분석 에도 있는 문제의 변형인 것 같다. CtCI에서는 글자 단위를 1개로 한정하고, 숫자와 문자의 순서도 이 문제랑 다르다. 카카오 문제가 조금 더 어렵다.

 

이 문제는 aabbaccc 같은 문자열을 2a2ba3c 같은 방법으로 압축하는 알고리즘을 구현한다. 대신에 첫 번째 예시는 문자열을 1개 단위로 비교하고, 2개 단위로 비교할 수도, n개 단위로 비교할 수도 있다.

• 2개 단위 -> aa/bb/ac/cc -> aabbaccc
• 3개 ->  aab/bac/cc -> aabbaccc 

이런 식으로 비교해서 가장 짧은 길이를 반환하고, 아무것도 안되면 그냥 입력 문자열 길이를 반환한다.

 

내 풀이 방법은 다음과 같다. 

 

1. 일단 분할 단위를 만든다. for 문으로 만드는데, 최대 절편 길이는 문자열 길이의 절반 이하.(중요해서 볼드 + 밑줄+ 기울임)
2. 각 분할당 비교할 문자열 ret, 현재까지 중복갯수 counter, 이전 문자열 prev를 설정한다.
   1. python slice 를 이용하여 자르면서 비교하는데,
      1. prev와 지금 잘린 문자열이 같다 => counter +=1
      2. 다를 경우
         1. counter 가 1일 경우 ret에 문자열만 추가
         2. counter 가 2 이상일경우 ret에 문자열+counter 추가
   2. 이제 각 분할단위당 가장 짧은 길이를 min, answer를 이용해 비교한다.  min(answer, len(ret))

 

def solution(string):

    answer = 9123412341 # Nothing-up-my-sleeve 
    for sl in range(1,len(string)//2 +1):

        ret = ""
        counter = 1

        prev = string[:sl]

        for i in range(sl, len(string)+sl, sl):
            if prev == string[i:i+sl]:
                counter+=1
            else:
                if counter != 1:
                    ret = ret + str(counter)+ prev 
                else:
                    ret = ret + prev

                prev = string[i:i+sl]
                counter = 1

        answer = min(answer, len(ret))

    return min(answer, len(string))