[프로그래머스]문자열 압축

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

문제를 간단히 요약하자면 다음과 같다.

알파벳으로만 이루어진 문자열 s가 주어진다.

ababab는 반복되는 문자인 ab가 총 3번 반복되므로 3ab로 줄일 수 있다.

단, 반복되는 문자를 줄일 때는 반복되는 문자의 수가 같아야하며, 맨 앞을 줄이지 않으면 뒤는 줄일 수가 없다.

이 때, 문자열을 줄여서 만들 수 있는 길이의 최솟값을 반환해야 한다.

 

코드를 작성하기 위한 순서는 다음과 같다.

1. 최대로 줄일 수 있는 길이는 문자열의 길이의 절반이므로 len(s)/2까지 반복문을 설정해준다.

2. 줄인 문자열을 반환하는 것이 아닌 길이를 반환하는 것이므로 줄일 때마다 현재의 길이에서 빼주는 식으로 진행한다.

3. 반복되는 문자열의 크기가 1부터 len(s)/2까지 하나하나 비교한다.

4. 반복되는 문자열의 크기와 갯수를 구하여 전체 길이에서 빼준다.

5. min 함수를 사용하여 최솟값을 계속 업데이트 해준다.

def solution(s):
    answer = len(s)
    for i in range(1,int(len(s)/2)+1):
        now=len(s) #2번 : 현재의 길이이다.
        index=0 #문자열에서 원하는 구간을 자르기 위한 포지션값이다.
        while index<=len(s): #3, 4번
            temp=s[index:index+i] #길이가 i인 같은 문자열이 반복되는지 비교하는 작업이다. 
            index+=i #index에 i를 더하여 다음 문자열도 같은지 확인한다.
            cnt=0 #길이가 i인 같은 문자열이 몇 번 반복되는지 count해주는 변수이다.
            while index<=len(s): #while문을 한 번 더 사용하여, 문자열 s 끝까지 길이가 i인 문자열이 같은지 비교해준다.
                if temp==s[index:index+i]:
                    cnt+=1 #같다면 cnt++을 해준다.
                    index+=i
                else: #다르다면 반복문을 종료한다.
                    break
            if cnt>0:
                now-=cnt*i #길이가 i인 문자열이 cnt+1번 반복되므로 전체 길이는 cnt*i만큼 줄일 수 있다.
                if cnt<9: #cnt가 9면 해당 문자열이 10개이므로 '10a'로 표현해야하므로 일의 자리가 아닌 십의 자리 '10'이 추가되기에 +1을 해준다.
                    now+=1
                elif cnt<99:
                    now+=2
                elif cnt<999: 
                    now+=3
                else:
                    now+=4
            answer=min(answer,now) #5번 : 최솟값을 구하는 문제이므로 min을 사용하여 answer값을 업데이트해준다.
    return answer