[카카오 2020] 문자열 압축

●○○

 

[문제] 링크

1. 알파벳으로 구성된 문자열이 입력으로 주어진다.

2. 1개 이상의 단위로 문자를 자르고 연속되는 문자열을 압축하여 표현한다.

예) aabbaccc를 1개 단위로 압축했을 때 => 2a2ba3c

3. 이렇게 문자열을 압축했을 때, 압축된 문자열의 최소 길이를 구해라.

 

[풀이]

1. 문자열의 길이를 s라고 했을 때, s/2이상의 크기로 자르는 것은 의미가 없다. 따라서, 문자열을 자르는 크기는 1부터 s/2까지이다. 

2. 자르는 단위를 size라고 한다면 연속되는 지 확인할 단어 word = s[:size]로 두고 for문으로 size만큼 더하면서 문자열을 탐색해 나간다.

- 만약 다음 문자열이 word와 같으면 연속되므로 count에 1을 더해준다.

- 만약 문자열이 연속하지 않으면 지금까지 탐색한 정보를 result에 count + word로 더해준다.

3. 만들 수 있는 모든 압축된 문자열의 길이를 비교하여 최소값을 리턴한다.

 

[외울 것]

# 빈 문자열 선언
ret = ""
for i in range(size, len(s), size):
	# for~range()에서 3번째 매개변수의 의미는 해당 값만큼 건너뛰면서 탐색하겠다는 뜻
# 문자열에 문자를 더할 때는
ret += word

[코드]

def solution(s):

    def compress(size):
        ret = ""
        word = s[0:size]
        cnt = 1
        for i in range(size, len(s), size):
            cur = s[i:i+size]
            if word == cur:
                cnt += 1
            else:
                if cnt > 1:
                    ret += str(cnt)
                ret += word
                word = cur
                cnt = 1
        if cnt > 1:
            ret += str(cnt)
        ret += word
        return len(ret)

    # 자를 크기 Size를 1부터 N/2까지 정한다
    answer = len(s)
    for i in range(1, answer // 2 + 1):
        answer = min(answer, compress(i))

    return answer