[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 문자열 압축 by 파이썬(Python)

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

프로그래머스

 

LV2

 

문제이해 

문자를 일정 단위로 압축할 수 있다.

최대로 압축하는 한 경우의 문자열 길이를 찾아내기.

 

 

풀이법

파이썬의 리스트 슬라이싱을 활용해 문자열을 잘라내 압축 문자열을 만든다.

현재 문자열과 이전 문자열이 같다면 압축 성공

다른 경우에 한번도 압축이 되지않는다면 그대로 표시, 압축이 두번이상 되었다면 압축해서 표시해준다.

arr에 현재 i만큼 자르면서 만든 압축 문자열의 길이를 저장한다.

가장 짧은 길이를 반환한다. 

 

 

코드

def solution(s):
    arr =[]
    if len(s) == 1:
        return 1
    
    for i in range(1, len(s)+1):
        b = ''
        cnt = 1
        tmp=s[:i]
        # 현재 문자열을 i 만큼 자르면서 압축 문자열 만들기
        for j in range(i, len(s)+i, i):
            #현재 문자열 == 이전 문자열
            if tmp==s[j:i+j]:
                cnt+=1
            #이전 문자열과 다른경우
            else:
                #반복횟수가 1이아닌경우 반복횟수와 문자열 추가
                if cnt!=1:
                    b = b + str(cnt)+tmp
                #반복횟수가 1인 경우 문자열 추가
                else:
                    b = b + tmp
                # 현재 문자열로 초기화
                tmp=s[j:j+i]
                cnt = 1
            
        arr.append(len(b))
                       
    return min(arr)

 

시간 복잡도

O(n^2)