(2020 KAKAO Blind Recruitment) 문자열 압축

Problem

• 카카오 링크: https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/
• 문제 풀기: https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3#

카카오 홈페이지 코멘트

• 정답률: 25.9%
• 출제 의도
• 문자열을 다룰 수 있고, 아래 예시와 같이 문자열과 관련된 다양한 작업을 할 수 있는지 파악
• 문자열 자르기
• 부분 문자열 얻기
• 문자열 비교하기
• 문자열 길이 얻기
• 문제 풀이
• 첫 번째로 배치된, 가장 쉬운 문제입니다. 문자열 길이가 최대 1,000으로 제한이 크지 않기 때문에, 가능한 모든 방법을 탐색하면 됩니다. 문자열 길이가 N일 때, 길이가 N/2 보다 크게 잘랐을 때는 길이가 줄지 않습니다. 따라서 1 ~ N/2 길이로 자르는 방법을 모두 탐색한 후 그중 가장 짧은 방법을 선택하면 됩니다.

My solution

def solution(s):
    if len(s) < 3:
        return len(s)
    
    answer = len(s)    
    max_cand = int(len(s)/2)
    for interval in range(1, max_cand+1):
        start=interval
        res = []
        pre_s = s[0:interval]
        num = 1
        while True:            
            now_s = s[start:start+interval]
            if now_s == pre_s:
                num += 1
            else:                
                res.append([num,pre_s])        
                num = 1
                pre_s = now_s
        
            if start > len(s):
                break
            start += interval
        len_cand = 0
        for k in range(len(res)):
            if res[k][0] == 1:
                len_cand += len(res[k][1])
            else:
                len_cand += len(str(res[k][0]))
                len_cand += len(res[k][1])
        answer = min(answer, len_cand)
        
    return answer