[Python] 문자열 압축 - 2020 KAKAO BLIND RECRUITMENT

<문제 링크>

 

2020 KAKAO BLIND RECRUITMENT > 문자열 압축

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

 

---

<풀이>

 

각각의 패턴 크기(1, 2, 3...)로 압축된 문자열의 길이 중 가장 많이 압축된 문자열(이하 최소값)의 길이를 return하는 문제이다.

0번째 인덱스부터 패턴을 비교해야 하며 중복된 횟수가 1인 경우는 무시하고 2부터 표시한다.

모든 패턴을 검사할 때까지 큰 반복문을 돌려주고 그 안에 반복문에서 패턴과 문자열 매칭을 통해 {중복된 횟수+패턴}으로 압축해준다.

작동 시간을 단축시키고 싶었으나 매칭 과정에서는 힘들 것 같아 최소값을 구하는 과정을 줄이는데 초점을 맞췄다.

패턴이 일치하지 않아 word에 pattern을 추가하는 과정 다음으로 최소값과 len(word)를 비교해 최소값보다 크다면 바로 연산을 멈춰 작동 시간을 단축했다.

반복문이 끝난 후에 min(hub.values)를 통해 values들 중 최소값을 골라 return해서 문제를 해결했다.

 

---

<코드>

hub: {패턴길이:압축크기}

start: 매칭 시작 지점

word: 임시 단어

pattern: 현재 패턴

---

def solution(s):
    hub = {0:len(s)} # 압축 크기 저장소

    # START
    for i in range(1, len(s) + 1): # i == 패턴 범위
        start = 0
        stack = 0
        word = ""
        pattern = s[0:i]

        # START
        while(True):
            if start > len(s): # 시작점이 문자열을 넘으면
                word += s[start-i:]
                hub[i] = len(word)  # 압축 크기 저장 (2), (1) -> (2) 위치 변경시 시간 단축
                break

            if pattern == s[start:start+i]: # 패턴 일치하면 스택 쌓기
                stack += 1
            else:
                word += (str(stack) if stack > 1 else "") + str(pattern) # {중복 횟수+패턴}으로 압축
                stack = 1
                pattern = s[start:start+i] # 다음 패턴으로 넘기기
                if min(hub.values()) < len(word):  # 최소값보다 값이 크면 그냥 무시(종료)
                    break

            start += i # 시작점 변경
        # END

        # hub[i] = len(word) # 압축 크기 저장 (1)
    # END
    answer = min(hub.values()) # 정답

    return answer

# MAIN
s = input()

print(solution(s))