문자열 압축 (60057번) - 프로그래머스 (Programmers)

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

프로그래머스

 

 

프로그래머스 - 문자열 압축 (60057번)

자료구조&알고리즘 : Exhaustive Search (완전 탐색)

난이도 : Lv 2

 

def solution(s):
    miny = n = len(s)
    for thr in range(1, (n>>1)+1):
        acc = 0
        std = s[:thr]
        cnt = 1
        for i in range(thr, n, thr):
            if std == s[i:i+thr]:
                cnt += 1
            else:
                acc += thr if cnt==1 else thr+len(str(cnt))
                std = s[i:i+thr]
                cnt = 1
        acc += len(std) if cnt==1 else thr+len(str(cnt))
        miny = min(miny, acc)
    return miny

 

 

2020 KAKAO BLIND RECRUITMENT 기출문제이다.

완전 탐색을 통해, 가장 짧게 압축할 수 있는 문자열 길이를 찾는 문제이다.

 

문자열 s의 길이가 1000 이하라서, 완전 탐색으로 풀 수 있었다.

 

---

 

① 문자열을 자를 단위(thr)를, for 문을 통해 [1 ~ len(s)//2] 범위에서 하나씩 탐색한다.

 

 

 

② 각 thr에서, 문자열 s를 단위 길이(thr)만큼 잘라서 압축한 뒤의 길이를 확인한다.

 

중복 횟수(cnt)가 1이면, acc에 [ 단위 길이(thr) ] 를 더해주고

cnt가 1보다 크면, acc에 [ 단위 길이 + len(str(중복 횟수)) ] 를 더해준다.

 

그리고 acc와 miny 중, 더 작은 값으로 miny를 업데이트 한다.

 

 

 

③ 압축한 길이가 가장 짧았던 경우의 길이를 출력한다. (miny)