[Seop's의 코드풀이] 프로그래머스 문자열 압축(2020 KAKAO BLIND RECRUITMENT) - Python

이번에 풀어볼 문제는 2020 KAKAO BLIND RECRUITMENT 코딩 테스트에서 

출시되었던 문자열 압축이란 문제입니다. 문제의 내용을 보면 다음과 같습니다.

 

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

프로그래머스

 

제 국어력이 부족한지 문제를 이해하는 데만 시간이 좀 걸렸습니다 ㅋㅋ

저와 비슷하신 분들을 위해 제가 그나마 좀 쉽게? 정리해 드리자면 

다음과 같은 문자열이 있다고 생각해 보겠습니다.

 

abababcdcdefg

 

압축하는 수	압축 해서 나온 문자열
0	abababcdcdefg
1	abababcdcdefg
2	3ab2cdefg

 

2개 까지만 진행을 하면 위 표와 같이 결과가 나오게 됩니다.

압축하는 수가 0인 경우는 입력된 문자열 그대로를 출력하게 됩니다.

압축하는 수가 1인 경우는 위 문자열에서는 변화가 없지만

aabb 와 같은 문자열에서는 2a2b로 압축되게 됩니다.

압축하는 수가 2인 경우는 2개씩 묶어서 압축을 진행하게 됩니다.

3ab2cd 여기까진 압축이 되었고 그 이후에는 압축이 되지 않으므로 그대로 내비 둡니다.

 

이런식으로 압축을 진행 한 후 가장 적은 문자열의 길이를 찾는 문제입니다. 

 

저는 본 문제를 풀때 압축하는 수에 중점을 두어서 문제를 풀었습니다.

위의 문자열로 예시를 들자면

1 : a

2: ab

3: aba

...

이런식으로 temp 라는 변수에 저장 한 후에 그 다음 것과 비교를 진행 했습니다.

그리고 일치한다면 숫자를 세는 cnt 변수를 증가시키도록 하는 작업을 진행하였습니다.

 

이제 반복적으로 돌리는 작업만을 진행하면 되지만

최대로 압축할 수 있는 경우는 (주어진 문자열의 길이)/2 만큼 입니다.

즉 길이가 8인 문자열은 4+4 까지만 압축이 가능합니다.

 

이 두가지에 초점을 맞추고 문제를 풀었고

코드의 자세한 설명은 코드에 주석으로 추가하였습니다. 

좀 더 발전 할 수 있는 방법이 있다면 댓글 달아주시면 감사하겠습니다.

감사합니다.

 

def solution(s):
    answer = 0
    ans_list = [len(s)]

    #  입축할 수 있는 최대 길이는 문자열 길이의 1/2 임
    for w in range(1, len(s)//2 + 1) :
        #  초기 비교한 문자열 저장
        temp = s[:w]
        cnt = 1
        buf = ""
        i = w 
        while i < len(s) :
            #  i + w 가 문자열보다 길 경우 하나씩 넣어주는 작업 진행
            if i + w > len(s) :
                buf += s[i]
                i += 1
            else :
                #  앞뒤가 같으면 cnt 값 하나씩 증가, i 값은 w 값 증가시킴
                if temp == s[i:i+w] :
                    cnt += 1
                    i = i + w
                else :
                    # 앞뒤가 일치해서 cnt 값이 1 이상인 경우 cnt 값 까지 포함해서 문자열 생성
                    if cnt != 1 :
                        buf += str(cnt) + temp
                        cnt = 1
                    else :
                        #  다른 경운 cnt 빼고 temp 만 문자열에 추가
                        buf += temp
                    # tmep 값 업데이트 
                    temp = s[i:i+w]
                    i = i + w

        # 마지막 부분 넣어주기
        if cnt != 1 :
            buf += str(cnt) + temp
        else :
            buf += temp
        #  buf 문자열의 길이만 답에 업로드
        ans_list.append(len(buf))
    #  정답에는 최솟값 출력
    answer = min(ans_list)
    return answer