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

문제출처: https://programmers.co.kr/learn/courses/30/lessons/60057

접근법

• 풀이 시간: 30분

카카오 채용 기출문제이고 난이도는 프로그래머스 기준 Level 2이다.
반복되는 문자열 "abcabc" -> "2abc" 와 같이 얼마나 주어진 문자열을 압축할 수 있냐를 물어보는 것인데 단순구현 문제였지만 로직이 쉽게 짜지지 않았던 것 같다.

1. 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 라는 조건 덕분에 문자열을 앞쪽부터 정해진 길이만큼 확인해주면 된다. 가장 바깥쪽 while문에서 sliding window를 1~(문자열길이-1)까지 증가시키면서 확인했다. ( sliding box가 사실 문자열 길이의 절반이 넘어가면 문자열을 압축할 수 없기 때문에 while(count <= len(s) + count ) 로 수정해도 통과 가능했다. )

2. 문자열 s에서 변수 start index부터 시작하여 sliding window 크기만큼 비교할 문자열 s1을 설정하고 window 크기만큼 옮겨가며 같은 지 비교해주었다. 이때 index가 문자열 s의 크기를 넘어가는 예외를 방지해주고 만약 같은 문자열을 찾았다면 총 몇 개를 찾았고 중복되는 횟수로 인해 압축된 문자의 개수를 계산하여 결과에서 빼주었다.

	result -= total*count - (count+ len(str(total)) )

3. 서로 크기가 다른 sliding window 중 가장 문자열 압축률이 낮은 정답을 리턴

코드

def solution(s):
    answer = len(s)
    count = 1
    while(count < len(s) ):
        result = len(s)
        start = 0
        while( start+1+count < len(s) ):
            s1 = s[start:start+count]
            n = start+count
            total = 1
            while( n+count <= len(s) and s[n:n+count] == s1 ):
                total += 1
                n += count
            if( total > 1 ):
                result -= total*count - (count+ len(str(total)) )
            start = n
        answer = min(result,answer)
        count += 1
    return answer