Level 2. 문자열 압축

Pear_Mh·2021년 6월 19일

알고리즘 프로그래머스

Programmers-Level 2.

목록 보기

7/40

07. 문자열 압축

코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 문자열 압축
https://programmers.co.kr/learn/courses/30/lessons/60057

문제 설명

Input value =

s = 알파벳 소문자로 이루어진 문자열

Process =

반복되는 문자열을 압축하라

Output value =

최대 압축된 문자열의 길이

제한 사항

s의 길이는 1 이상 1,000 이하입니다.
s는 알파벳 소문자로만 이루어져 있습니다.

문제 구상

#00
s = "aabbaccc"

1부터 문자열의 길이를 기준으로 문자열을 나눈다.

#01
answer = []
for i in range(1,len(s)+1):

빈 array를 생성하여 나누는 길이 기준으로 리스트를 구성한다.

#02    
	array = []
    for j in s:
        if len(array)==0 or len(array[-1][0])==i:
            array.append([j,1])
        else:
            array[-1][0]+=j

만들어진 리스트의 원소가 같을 경우 해당 원소를 삭제하고 원소의 1번째 위치에 +1 한다.

#03    
    sumss = []
    for k in array:
        if len(sumss)==0 or k[0] != sumss[-1][0]:
            sumss.append([k[0],1])
        else:
            sumss[-1][1]+=1

나눈 길이를 cnt에 더하고, 1번째 원소 값이 2 이상일 경우 cnt에 1을 더한 뒤 answer리스트에 삽입한다.

#04    
    count = 0    
    for q in sumss:
        count+=len(q[0])
        if q[1] > 1:
            count+=len(str(q[1]))
    answer.append(count)

최종 리스트의 최소값을 구한다.

#05
min(answer)

문제 풀이

def solution(s):
    answer = []
    for i in range(1,len(s)+1):
        array = []
        sumss = []
        count = 0
        
        for j in s:
            if len(array)==0 or len(array[-1][0])==i:
                array.append([j,1])
            else:
                array[-1][0]+=j
        

        for k in array:
            if len(sumss)==0 or k[0] != sumss[-1][0]:
                sumss.append([k[0],1])
            else:
                sumss[-1][1]+=1
        
        for q in sumss:
            count+=len(q[0])
            if q[1] > 1:
                count+=len(str(q[1]))
        answer.append(count)
    return min(answer)