[프로그래머스] 코딩테스트 연습2020 KAKAO BLIND RECRUITMENT - 문자열 압축

문제

문제 설명

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

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

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

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

 

입력 & 출력

입출력 예

sresult

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

새로 사용한 함수

새로 사용한 것은 아니지만 [ : ] 슬라이싱 하는 것

그리고 for문 문법에서 range( 시작, 끝, 반복 크기 ) 리마인드

 

풀이 과정

프로그래머스가 쉬운것도 많다는 이야기를 들었었지만 2단계 문제도 많이 어려웠다.

1. 문자열을 처음부터 한 개씩 길이를 늘리면서 해당 내용과 같은 문자열이 있는지 확인해야 한다. 슬라이싱을 이용한다.

tmp = s[시작 : 끝] , for문에서 마지막 숫자 전까지를 계산하는 것과 같이 이것도 마지막 숫자에서 1을 뺀 값까지 계산

2. 1번의 슬라이싱 방법을 이용하여 for문을 순회 1부터 시작하여 1씩 증가하면서 문자열을 만들어준다. 글자가 1개인 문자열 2개인 문자열 3개인 문자열.... 을 순서대로 뽑아준다.

3. 이렇게 문자열을 뽑아주게 되면 시작값이 해당 문자열인 for문을 한 개 더 실행시켜준다. 이렇게 했을 때 cnt의 숫자는 문자열을 자르면서 비교할 것을 만들었어도 1개가 있는 것이므로 1로 설정한다.

4. cnt가 1일때는 해당 문자열 앞에 1을 써줄 필요가 없으므로 1일 때의 예외 처리를 해줄 필요가 있다. 같은 숫자인지 판별해줄 조건문을 만들고 같은 숫자가 아닐 경우에 cnt가 1인 경우와 아닌 경우의 분기점을 만들어준다.

5. 4번에서 같은 숫자일 경우에는 cnt를 1 증가시켜준다.

6. 모든 것이 끝날때는 이전 값으로 초기화를 시켜주고 for문을 순회한다.

7. 이렇게 만든 문자열의 길이는 나중에 가장 짧은 것을 확인해야 하기 때문에 배열에 저장하여 두고 min 함수를 이용하여 가장 짧은 경우의 값을 출력할 수 있게 한다.

 

코드

def solution(s):
    result = []
    for i in range(1, len(s) + 1):
        str_s = ''
        cnt = 1
        tmp = s[:i]

        for j in range(i, len(s) + i, i):
            if tmp == s[j:i + j]:
                cnt += 1
            else:
                if cnt != 1:
                    str_s = str_s + str(cnt) + tmp
                else:
                    str_s = str_s + tmp
                tmp = s[j:i + j]
                cnt = 1

        result.append(len(str_s))

    answer = min(result)
    return answer