프로그래머스 Lv. 2 문자열 압축 Python

문제 링크

https://school.programmers.co.kr/tryouts/72056/challenges

정답 코드

def solution(s):
    answer = 1001
    lenS = len(s)
    if lenS == 1:
        return 1
    for cut in range(1, lenS//2+1):
        stack = []
        length = [1 for _ in range(lenS//cut+1)]
        lengthIdx = 0
        string = ""
        for idx in range(lenS):
            alpha = s[idx]
            string += alpha
            if len(string) == cut:
                if stack:
                    if stack[-1] == string:
                        length[lengthIdx] += 1
                    else:
                        stack.append(string)
                        lengthIdx += 1
                else:
                    stack.append(string)
                string = ""

        plusLength = 0
        for kdx in range(lengthIdx+1):
            nowLength = length[kdx]
            if nowLength // 1000:
                plusLength += 4
            elif nowLength // 100:
                plusLength += 3
            elif nowLength // 10:
                plusLength += 2
            elif nowLength > 1:
                plusLength += 1
        nowValue = len(stack) * cut + lenS % cut + plusLength
        if nowValue < answer:
            answer = nowValue
    
    return answer

풀이 방법

1. 1000자 이하의 문자를 자를 때 1 ~ 500의 길이로 자를 수 있다.
   1. 따라서 cut의 범위를 1 ~ lenS//2 + 1
2. cut의 길이만큼 자른 문자열이 stack에 들어간다.
   1. stack이 존재하면 마지막 문자열과 비교한다.
      1. 같으면 length의 lengthIdx 번째에 +1을 해준다.
      2. 다르면 lengthIdx를 +1해주고 stack에 넣는다.
   2. stack이 존재하지 않으면 그냥 넣는다.
3. 마지막으로 현재 압축된 문자열의 길이를 계산한다.
   1. stack의 길이 * cut
   2. lenS를 cut으로 나눈 나머지
   3. plusLength를 더해준다.
      1. 여기서 plusLength는 a가 1000개 일 때 "1000a"로 압축 되기 때문에 압축된 문자열의 길이에 따라서 다르게 적용한다.
         1. 1000a는 4을 더해주고
         2. 100a라면 3을 더해준다.
         3. 10a라면 2를 더해준다.
         4. 당연히 1a는 더해주지 않고 2a 부터 1을 더해준다.

 

느낀점

- 방문배열 등의 배열을 사용할 때 초기값을 설정하는 것에 주의하자.