[Level 2] 문자열 압축

programmers.co.kr/learn/courses/30/lessons/60057

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

---

접근

길이가 1부터 입력된 문자열의 반만큼의 길이를 갖는 패턴문자를 생성하여 처음부터 탐색을 진행한다.

이 문제에서는 인덱스를 잘 설정해주는 것이 관건이다. 어디서부터 어디까지 잘라서 비교할지 신경을 써야한다.

그렇게 비교를 하다가 패턴문자와 다르다면 지금까지의 패턴의 개수와 패턴을 문자열에 추가해주고 패턴문자를 새롭게 갱신해주도록 한다.

 

구현

먼저 answer에는 입력받은 문자열의 길이를 담아서 나중에 최솟값 비교에 사용한다.

이후 길이가 1 부터 문자열의 반이 되는 길이까지 순서대로 잘라서 패턴 문자와 비교를 한다.

초기에 패턴문자 pat는 처음부터 자를 만큼까지 슬라이싱하여 넣어주고,

탐색이 진행될 때 사용되는 인덱스인 idx를 i로 초기화한다. 또한 패턴문자의 개수를 카운트할 cnt를 1로 초기화 하였다.

 

이후 while문에서 탐색을 진행한다.

temp에 pat와 비교할 문자를 슬라이싱하여 저장하고 비교를 진행한다.

같다면 패턴의 개수인 cnt를 +1하고 다음 인덱스를 자를 길이만큼 증가시킨다.

다르다면 지금까지의 패턴의 개수와 패턴문자를 word에 추가하고 새로운 패턴 문자를 만들어준다.

 

마지막에 while문으로 탐색을 진행하고 마지막 패턴은 word에 담기지않고 while문이 종료된다.

따라서 마지막 패턴을 word에 담고 word의 길이로 answer와 최솟값을 찾기위한 비교를 한다.

def solution(s):
    answer = len(s)
    for i in range(1, len(s) // 2 + 1):
        word = ''
        pat = s[:i]
        idx = i
        cnt = 1
        
        while idx < len(s):
            temp = s[idx:idx + i]
            
            if pat == temp:
                cnt += 1
                idx += i
            else:
                if cnt == 1:
                    cnt = ''
                word += str(cnt) + pat
                pat = s[idx:idx + i]
                idx += i
                cnt = 1
        if cnt == 1:
            cnt = ''
        word += str(cnt) + pat

        answer = min(answer, len(word))
    return answer