[Programmers] - 문자열 압축 (Level 2)

Programmers Coding Test : 2020 KAKAO BLIND RECRUITMENT

안녕하세요, 이번 포스팅은 2020 카카오 블라인드 채용에 출제되었던 문제입니다.
문자열을 가장 효율적으로 압축했을때의 길이를 반환하는 문제였는데요.
지체 없이 문제 설명 들어가겠습니다!

문제 설명

데이터 처리 전문가가 되고 싶은 “어피치”는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 “aabbaccc”의 경우 “2a2ba3c”(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, “abcabcdede”와 같은 문자열은 전혀 압축되지 않습니다. “어피치”는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, “ababcdcdababcdcd”의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 “2ab2cd2ab2cd”로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 “2ababcdcd”로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, “abcabcdede”와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 “abcabc2de”가 되지만, 3개 단위로 자른다면 “2abcdede”가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

s	result
“aabbaccc”	7
“ababcdcdababcdcd”	9
“abcabcdede”	8
“abcabcabcabcdededededede”	14
“xababcdcdababcdcd”	17

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 “abcabcabcabc6de” 가 됩니다.
문자열을 3개 단위로 자르면 “4abcdededededede” 가 됩니다.
문자열을 4개 단위로 자르면 “abcabcabcabc3dede” 가 됩니다.
문자열을 6개 단위로 자를 경우 “2abcabc2dedede”가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다. 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다. 이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

문제 풀이

이번 문제는 시행착오가 꽤 있어서 개인적으로 힘들었던 문제였습니다 ㅠㅠ.
테스트는 통과했는데 실제 채점시에는 틀리는 경우가 발생했기 때문인데요, 어떤 케이스에서 틀렸는지 찾는데 시간을 정말 많이 쓴 것 같습니다 ㅠㅠ.

단순 문제풀이를 위해서 쉽게 가려고 잔머리를 좀 굴렸더니, 바로 이런 벌을 받게 되는건가 싶기도 하더라구요.

힘들었던 만큼 이번에는 제 풀이를 조금 상세하게 설명해보려고 합니다.
최종 풀이 코드는 아래와 같습니다.

s ="abcabcabcabcdededededede"

def solution(s):
    answer = len(s)
    for i in range(1, round(len(s)/2)+1):

        #문자리스트 만들기
        temp = []
        for j in range(0, round(len(s)/i)):
            temp.append(s[j*i:(j+1)*i])


        #반복문자열 찾기
        rep_tmp = 0
        rep = []
        for k in range (1,len(temp)):

            if temp[k] == temp[k-1]:           
                rep_tmp +=1

            elif temp[k] != temp[k-1]:
                if rep_tmp>0:
                    rep.append(rep_tmp)
                    rep_tmp = 0

            if  k == len(temp)-1:
                if rep_tmp>0:
                    rep.append(rep_tmp)

        strcnt = [str(c+1) for c in rep]
        count = len(s) - (sum(rep)*i) + len(''.join(strcnt))
        answer = min(answer, count)

    return(answer)

solution(s)

14

우선, 초기 answer를 입력받은 문자열 s의 개수로 지정해주었습니다.
다음으로, 문자열을 n개 단위로 압축해야 하므로 이에 따라 1부터 round(len(s)/2)+1까지 for loop를 만들었습니다.
가장 큰 단위로 압축하는게 전체 문자열의 절반 길이만큼 압축하는것이므로 round(len(s)/2)+1을 써주었습니다.

다음으로, n개 단위로 압축하기 위해서 문자열을 n개 단위로 자른 문자리스트를 만들어 주었습니다.
예를 들어 s = ‘ababcdcd’라고 하면, 아래와 같이 출력 결과를 얻을 수 있습니다.

s ="ababcdcd"

for i in range(1, round(len(s)/2)+1):

    #문자리스트 만들기
    temp = []
    for j in range(0, round(len(s)/i)):
        temp.append(s[j*i:(j+1)*i])

    print(temp)

['a', 'b', 'a', 'b', 'c', 'd', 'c', 'd']
['ab', 'ab', 'cd', 'cd']
['aba', 'bcd', 'cd']
['abab', 'cdcd']

총 문자열의 길이가 8개이므로 for loop을 돌면서 절반 길이인 4개 단위까지 문자리스트를 만들어 내는 것을 확인할 수 있습니다.

다음으로, 반복되는 문자열을 count해주어야 하는데요, 위에서 만들어진 문자 리스트에서 [‘ab’, ‘ab’, ‘cd’, ‘cd’]를 예로 들어 보겠습니다.

두번째 element에 있는 ‘ab’부터 시작해서, 그 전의 element와 같은지 비교하고 만약 같으면 rep_tmp에 1을 더해줍니다. 첫번째 element도 ‘ab’이므로, ‘ab’패턴에 대한 rep_tmp는 1이 늘어나게 됩니다. 이 부분을 구현하면 아래와 같습니다.

if temp[k] == temp[k-1]:           
    rep_tmp +=1

그런데, 세번째 element인 ‘cd’와 그 전의 element인 ‘ab’는 서로 다릅니다.
따라서, ‘ab’패턴에 대한 반복 횟수를 저장해왔던 rep_tmp가 0보다 크면 rep_tmp를 rep에 업데이트 해주고, rep_tmp는 초기화해줍니다. 지금부터는 ‘cd’패턴에 대한 반복횟수를 rep_tmp에 업데이트 하게 됩니다.
이 부분을 구현하면 아래와 같습니다.

elif temp[k] != temp[k-1]:
    if rep_tmp>0:
        rep.append(rep_tmp)
        rep_tmp = 0

만약 마지막 element인 ‘cd’에서 그 전의 element와 반복되는 경우, ‘cd’패턴에 대한 반복횟수인 rep_tmp가 rep에 업데이트 되지 않습니다. 이를 방지하기 위해서 조건문을 아래와 같이 하나 더 추가했습니다.

if  k == len(temp)-1:
    if rep_tmp>0:
    rep.append(rep_tmp)

마지막으로, 압축된 문자열 개수를 세어주어야 합니다.

n개 단위로 압축된 문자열 개수는,

원래 문자열 개수 길이 - (패턴과 상관없이 총 반복된횟수 * n) + 반복패턴개수를 나타내는 숫자자리 수

입니다.

‘ababcdcd’의 경우 2개 단위로 압축하면 , 8 - (2 * 2) + 2 = 6이 됩니다.

rep에는 패턴별로 반복된 횟수가 저장되어 있습니다. 만약 ‘ababcdcd’를 2개 단위로 압축했다면 ab패턴에서 한번, cd 패턴에서 한번이므로 [1,1]로 저장되어 있을겁니다. 반복패턴개수를 나타내는 숫자자리 수는 반복 횟수보다 1씩 크므로, rep의 각 element보다 1이 큰 [2,2]가 되겠죠.

이를 이용해서 압축된 문자열 개수를 구하는 식을 세우면 아래와 같습니다.

strcnt = [str(c+1) for c in rep]
count = len(s) - (sum(rep)*i) + len(''.join(strcnt))

위에서 strcnt는 반복패턴개수를 나타내는 숫자를 나타내며, len(‘‘.join(strcnt))를 통해 이에 해당하는 숫자자리 수를 구할 수 있습니다.

마지막으로, 기존 s의 문자열 길이와 비교해서 더 압축된 문자열 길이가 더 작다면, answer를 업데이트 해주고 마무리합니다.

answer = min(answer, count)

생각보다 시간이 많이 걸려서 조금 당황했지만, 그래도 한 문제에서 많은 것들을 배울 수 있었습니다.
더욱 훌륭한 풀이들이 많을테니까, 저도 더욱 성장해보도록 하겠습니다.

그럼 다음 포스팅에서 뵙겠습니다!