프로그래머스 문자열 압축 Level 2

https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3 

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "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. 2중 반복문을 이용해 처음에는 한자리씩 그다음은 두자리씩 .,.. i의 크기만큼 나누어 비교하는 방법을 이용한다

2. 반복문 내에 이전 문자열과 이후 문자열을 계속 비교하며 서로 다를 때까지 count를 센다.

3. 만약 다르게 되면 count 크기를 비교해 2이상이면  압축한 문자열을 추가한다.

4. 1이하이면 그냥 압축을 못했으므로 그냥 문자열을 추가한다.

5. 계속 반복하며 가장 작은 크기의 문자열을 정답으로 return 한다. 

 

내가 작성한 소스코드

def solution(s):
    answer = 1000
    for i in range(1,int(len(s)/2)+2): # 1~ 문자열 크기의 절반 +2까지
        zipString = "" #추가할 문자열 초기값
        zipCount=1 #초기 문자열 크기 
        preStr = s[0:i]  #초기 문자열 
        for j in range(i,len(s)+1,i): # i 크기만큼 나누어서 문자열 비교함 
            nextStr = s[j:j+i]
            if preStr == nextStr:
                zipCount += 1
            else:
                if zipCount >= 2:
                    zipString = zipString + str(zipCount) + preStr
                else:
                    zipString = zipString + preStr
                zipCount = 1
                preStr = nextStr
        zipString += preStr
        
        if answer > len(zipString):
            answer = len(zipString)
            
    return answer

 

 

이중 폴문을 통해 이전값과 이후값을 비교하며 카운트하는 방법을 이용했다. (처음에 한자리씩  그 이후 하나씩 늘어나며 최대 문자열 크기의 절반만큼의 크기까지 비교한다 그 이상은 이전값과 이후 값이 크기가 다르기 때문에 비교할 필요가 없어진다. 

 

그렇게 이전값과 이후값이 달라질때까지 count를 하고 달라지는 순간 count의 크기를 비교해 중복된 값이 있으면 압축한 문자열을 넣어주고 아니면 그냥 문자열을 넣어준다. 그 작업이 끝나면 answer에 입력 돼 있는 문자열의 크기와 비교 후 더 적으면 answer에 적은 값을 대입하여 반복 후 answer을 정답으로 return한다

 

결론 및 고찰 

문제를 이해하는데 조금 고민을 했었다. 처음에는 for문의 range설정을 하는데 애를 먹었다. 왜냐하면 슬라이스를 이용하는데 어떠한 값을 넣어줘야할지 몰랐기 떄문이다. 하지만 구글링을 하지 않고 고민 끝에 풀었다는 것에 만족했다. 그런데 또 아쉬웠던 점이 이 문제를 풀고 검색을 했는데 카카오 1번문제였다 ㅋㅋ(정답률은 25%긴하지만) 그래도 내 지식만으로 풀었다는 것에 의의를 두자

 

소요 시간 87분