프로그래머스 문자열 압축

2020 KAKAO BLIND RECRUITMENT 문제

위의 카카오 공식 해설을 참조하시면 좋을 것 같습니다.

 

문제 풀이

1. 압축하는 글자 수는 1개부터 글자수의 절반까지만 하면 됩니다.

2. 압축 글자 수를 num이라 할 때, 첫 문자열의 위치를 i, 다음 문자열의 위치를 j라 하면 s[i:i+num]와 s[j:j+num]을 비교하며 같으면 j를 j+num으로 고쳐주며 같은 단어의 수를 세어줍니다.

3. 다른 경우에는 정답 문자열에 같은 단어의 숫자 + s[i:i+num]을 더해줍니다.

4. 위의 과정을 반복한 후, 남은 문자열을 더해줍니다. (xxxxi를 압축하는 경우, 위의 과정을 반복하면 2xx가 되고, 남는 i를 더해 2xxi를 완성합니다.)

Python Code

def solution(s):
    answer = len(s)
    for i in range(1,len(s)//2+1):
        tmp = compress(i,s)
        answer = min(answer,tmp)
    return answer
 
 
def compress(num,s):
    ans = ''
    i = 0
    j = num
    cnt = 1
    while i<len(s):
        if s[i:i+num] == s[j:j+num]:
            cnt += 1
            j += num
            if j + num > len(s):
                ans = ans + str(cnt) + s[i:i+num] if cnt != 1 else ans + s[i:i+num]
                ans += s[j:]
                break
        else:
            ans = ans + str(cnt) + s[i:i+num] if cnt != 1 else ans + s[i:i+num]
            i = j
            j += num
            cnt=1
            
    return len(ans)

Line 3 : 압축은 1개부터 문자열의 절반까지만 수행합니다.

Line 11 : i는 기준 문자열의 시작점입니다.

Line 12 : j는 비교할 문자열의 시작점입니다. 처음에는 s[0:num]과 s[num:num+num]을 비교하게 됩니다.

Line 13 : cnt는 기준 문자열이 반복되는 횟수입니다. 반복되는 문자열이 없는 경우에는 1이 됩니다.

Line 14 : 기준 문자열의 시작점이 문자열보다 커지면 중단합니다.

Line 15 : 기준 문자열이 반복되면 cnt에 1을 더해주고, j에 num을 더해 다음 문자열을 기준 문자열과 비교합니다.

Line 19 : cnt가 1인 경우에는 쓰지 않습니다.

Line 20 : 위의 과정4인 남는 문자열을 씁니다.

 

문제 링크

코딩테스트 연습 - 문자열 압축