문자열 압축 [2020 KAKAO BLIND RECRUITMENT]

https://school.programmers.co.kr/learn/courses/30/lessons/60057

문제 분석

• S의 길이는 1 이상 1000 이하이다.
• 그렇다면 수행 시간은 O(N^2)까지 허용된다.
• 문자열은 제일 앞에서부터 정해진 크기만큼 잘라야 한다.

알고리즘 설계

• 1부터 S의 길이/2만큼 첫 번째 반복을 수행한다.
• S의 길이/2 이상이 될 경우 결과값에 영향을 주지 않으므로 범위를 제한한다.
• 두 번째 반복문을 돌리며 해당 길이로 S를 쪼개며 비교를 수행한다.
• 첫 번째 단어를 기준으로 다음 단어와 비교하며 나아간다.
• 단어가 동일하다면 카운트를 증가시키고, 다르다면 카운트를 기준으로 해당 루프의 길이 값을 증가시킨다.
• 두번째 루프를 모두 돌았다면, 남은 문자를 처리한다.
• 해당 루프의 길이 값이 더 적다면 값을 교체하고 다음 루프로 이동한다.

정답 코드

input = "abcabcabcabcdededededede"


def string_compression(string):
    string_len = len(string)

    for i in range(1, len(string) // 2):
        first_word = string[:i]
        compare_len = 0
        count = 0
        for j in range(i, len(string), i):
            compare_word = string[j:j + i]
            if first_word != compare_word:
                if count != 0:
                    compare_len += 1 + len(first_word)
                else:
                    compare_len += len(first_word)
                count = 0
                first_word = compare_word
            else:
                count += 1

        if count != 0:
            compare_len += 1 + len(first_word)
        else:
            compare_len += len(first_word)

        if compare_len < string_len:
            string_len = compare_len

    return string_len


print(string_compression(input))  # 14 가 출력되어야 합니다!

print("정답 = 3 / 현재 풀이 값 = ", string_compression("JAAA"))
print("정답 = 9 / 현재 풀이 값 = ", string_compression("AZAAAZDWAAA"))
print("정답 = 12 / 현재 풀이 값 = ", string_compression('BBAABAAADABBBD'))

결과

회고

• 해당 문제의 경우 문자열의 길이를 맨 처음부터 정해진 길이로 잘라 모든 경우의 수를 단순 반복 비교하는 문제였기 때문에 난이도가 그다지 까다롭지는 않았다.
• 문자열 슬라이싱 및 경계 처리에 대해 이해하고 있는지에 대해 묻는 문제라고 느껴졌다.
• 다만, 쪼개진 문자열을 비교하고 처리되지 않은 마지막 문자열에 대한 처리를 해야한다는 생각을 못해서 정답을 도출해내는데 상당히 시간이 소요되었다.