코딩테스트 준비 - 프로그래머스: 문자열 압축 풀이+상세 (파이썬)

---

프로그래머스: 문자열 압출 풀이

---

문제 풀러 가기

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 함수를 완성해주세요.

---

풀이

1. 처음에는 하나씩 쪼개고, 그다음 두 개씩, 세 개씩 쪼개는 형식으로 for문을 돌린다.

2. 그중 길이가 제일 작은 값은 return 한다. 

---

코드

def solution(s):
    result=[]
    if len(s)==1:
        return 1
    for i in range(1, (len(s)//2)+1):
        b = ''
        cnt = 1
        tmp=s[:i]

        for j in range(i, len(s), i):
            if tmp==s[j:i+j]:
                cnt+=1
            else:
                if cnt!=1:
                    b = b + str(cnt)+tmp
                else:
                    b = b + tmp
                tmp=s[j:j+i]
                cnt = 1
        if cnt!=1:
            b = b + str(cnt) + tmp
        else:
            b = b + tmp
                
        result.append(len(b))
    return min(result)

---

코드 풀이

* 이해가 안 되거나 더 자세한 풀이를 원한다면 더보기를 클릭하세요 :)

1. result는 쪼갠 문자열의 길이들을 담는 list

예를 들어, 

1씩 쪼겠을 때 길이가 7이면 7을 result에 담음

2씩 쪼겠을때 길이가 8이면 8을 result에 담음

 

2. len(s)==1 , 문자열 s가 1일 때 반환 값은 항상 1.

 

3. range(1, (len(s)//2)+1) 은 쪼갤 수 있는 최대 길이가 문자열 s의 반.

예를 들어,

b = "aabbaccc"일 경우

"aabb", "accc" 이렇게 문자열 길이의 반이, 쪼갤 수 있는 최대 길이이다.

그 이상 쪼개면 index out of range 에러남.

 

b="aabbaaccc" 같이 홀수인 경우도 마찬가지로, 

len(b)=9,  len(b)//2 = 4이므로 4가 쪼갤 수 있는 최대 길이다.

5씩 쪼개면 10 이상이 되므로 index가 범위를 벗어나게 돼서 오류.

 

4. b= ' ' : b문자열 안에는 매번 쪼갰을 때 나오는 문자열을 저장함. 

예를 들어,

s="aabbac"를 1로 쪼갤 경우, 

최종적으로 "2a2bac"가 나온다. 

이문자 열을 b에 저장한다. b="2a2bac"가 됨.

두 번째 for문이  끝날때, len(b)를 result에 추가해준다.

 

첫 번째 for문이 시작할 때 항상 b=''으로 리셋을 시켜, 

다음 s를 2로 쪼갰을 경우의 문자열을 b에 담을 준비를 해준다.

 

5. cnt = 1, 문자열이 연속으로 반복되는지 체크하는 숫자.

예를 들어,

s = "aabbac" 일 경우,

첫 번째 인덱스에 있는 문자는 무조건 tmp에 담는다.

tmp='a' 이므로, 일단 문자의 개수는 1부터 시작하므로, cnt는 0이 아닌 1부터 시작한다.

 

6. tmp = s[:i] 문자열을 쪼갤 때 처음 부분은 무조건 tmp에 넣어준다.

tmp는 그다음 문자열과 연속되는지 보기 위한 변수다.

예를 들어,

s='aabbac'이며, 1씩 문자열을 쪼갤 때,

쪼갠 후의 첫 번째 문자를 무조건 tmp에 넣어줘야지 그다음 문자와 연속되는지 아닌지 체크할 수 있다.

s의 첫 번째 인덱스가 'a'이므로 , tmp= 'a'

 

if tmp==s[:i]

이때, s의 그다음 인덱스에 있는 문자와 tmp에 있는 문자가 같으면, cnt 변수를 1씩 증가시키고,

패스 한다.

 

if tmp!=s[:i]

이때, s의 그다음 인덱스에 있는 문자와 tmp에 있는 문자가 다르면, 

b변수에 지금까지 더한 cnt변수와, tmp에 있는 문자를 넣어준다.

b에 넣은 후, tmp에는 그 다른 문자를 넣어주고, cnt=1로 초기화해준다.

(b = b + str(cnt) + tmp)

(* 여기서 cnt가 1일 때는 생략하여 b에 넣어야 하므로, if문을 통해 cnt가 1일 때와 cnt는 1이 아닐 때를 나눠준다. )

tmp=s [j:j+i]

cnt=1

 

7. for j in range(i, len(s), i)는 i만큼 문자를 계속 쪼갠다.

첫 번째 for 문에서 i=1일 때,

두 번째 for 문은 "for j in range(1, len(s), 1)" 이 되는데, 

이 말은 즉, j = 1~len(s)까지, 1씩 건너 띈다는 소리다.

예를 들어 len(s)=5이면 

j = 1,2,3,4가 된다. (5는 포함하지 않음.)

 

그러면 i=2 일 때, "for j in range(2, len(s), 2)"일 경우,

2부터 시작하고 2씩 건너뛰었으니 j=2,4가 된다.

 

8. 두 번째 for문이 끝나고 그 뒤에 또 cnt!=1 은,

마지막 , tmp에 담은 문자를 b변수에 추가해주기 위해서이다.

예를 들어,

s = "aabbac"일 경우, 

두 번째 for 문에서 마지막 문자를 돌릴 때, 

i = 3,

for j in range(3, len(s), 3) 이 된다. 

이때, b= "2a2b"가 들어가 있으며, tmp = 'a' <-s[-2] 가 들어가 있다.

두 번째 for문의 if, else문에서  tmp와 s의 마지막 인덱스에 위치한 'c'와 다르므로 

tmp가 b에 추가되며, tmp에는 'c'가 담기게 되며 for 문이 끝난다. (b="2a2ba"가 됩니다.)

 

하지만 우리가 원하는 결과는 "2a2bac"이므로,

마지막 c를 추가해줘야 되는데, for문 밖에서 

위와 마찬가지로 cnt가 1일 때와 아닐 때를 if, else문으로 구분하여 추가해준다.

 

도움이 되셨다면 하트 꾹 눌러주세요 :)