[프로그래머스][2020 KAKAO BLIND RECRUITMENT][Python] 문자열 압축

[ 문제 ]

 

• 문제 풀러 가기

---

[출제 의도]

 

• 문자열을 활용

---

[ 문제 풀이 ]

 

문자열 길이가 N일 때, 분절 범위는 1부터 n/2입니다.

n/2를 넘어가게 되면 문자열을 줄일 수 없습니다.

 

문자열의 길이는 최대 1,000입니다. 따라서 완전 탐색을 해도 시간 초과가 나지 않습니다.

그래서 분절 범위마다 줄인 결괏값 중에서, 가장 짧은 길이를 찾았습니다.

 

주의할 점은 문자열 길이가 1이면 1을 반환합니다.

---

[ 정답 코드 ]

 

def solution(s):
    result = len(s) + 1

    for n in range(1, (len(s) // 2) + 1):  # 분절 범위
        cnt = 1
        tmp = len(s)
        check = True
        for i in range(0, len(s) - n + 1, n):  # 앞에서부터 분절
            if i == 0:
                pre = s[i:i+n]
                continue

            now = s[i:i+n]
            if pre == now:
                if check:  # 연속으로 중복되는 문자열, 1개 남기기
                    check = False
                    tmp += 1

                cnt += 1  # 연속 횟수
                tmp -= n  # 연속으로 중복되는 문자열 제거

                print(cnt)
                if cnt > 9 and cnt == int('1' + (len(str(cnt)) - 1) * '0'):  # 연속 횟수, 두 자리 이상
                    tmp += 1

            else:  # 불연속
                check = True
                cnt = 1
                pre = now

        result = min(result, tmp)
    return min(result, len(s))