[카카오][Python] 문자열압축

아래의 문제는 카카오 채용 코딩테스트 내용이며 코드는 직접 푼 내용입니다.

---

문자열압축 

문제상황

예를 들어, ababcdcdababcdcd 에 대한 리턴값을 찾는다고 하면 

1개단위로 자르면 ababcdcdababcdcd 

2개단위로 자르면 ab ab cd cd ab ab cd cd -> 2ab2cd2ab2cd

3개단위, 4개단위,, 등등 반복하다가 

8개단위로 자르면 ababcdcd ababcdcd -> 2ababcdcd 

이렇게 압축한 문자열들 중에 문자의 길이가 가장 짧은 문자를 찾는 것이다. 

요구사항

압축할 문자열 s가 매개변수로 주어질 때,

위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를

return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

입출력

---

풀이과정

1.N개 단위로 문자열 슬라이싱을 반복한다-> N의범위는? 최대가 절반인듯? 

1-1. 근데 자르다가 남는게 생기면 -> 뒤에다가 이어붙인다. 

2. 자른문자열을 가지고 압축문자열을 만든다. --> 그 자른 단위들이 몇개가 있는지 어떻게 계산할 것인가?

예를 들어 aaaabbcc를 2개씩 자른 압축문자열로 만들면 2aabbcc 가 된다. aa가 2개인걸 어떻게 알아내느냐!

추가로 bb가 1개, cc가 1개인데 압축문자열로 만들땐 1을 생략한다

3. 이렇게 N개 단위로 자른 문자열들을 모아서 그 중에서 가장 길이가 짧은 걸 리턴한다. 

 

크게보면 이런 요구사항을 해결해야한다. 

 

1. N개 단위로 문자열을 자른다.

우선, N의 범위를 구하기 위해 가장 큰 경우를 생각해보면 aabbaabbcc처럼 전체를 딱 반으로 나뉘는 경우다.

그래서 n의 전체범위는 1개단위로 자르는거부터, 전체길이의 절반의 개수까지가 된다. range()에는 len(s)//2+1이다. 

그리고 N개씩 문자열을 자른다. >>여기가 관건!

자르기 위해서 n개씩 증가하는 for문을 돌고, i부터 i+n까지 (문자열의 길이가 n개) 문자열을 슬라이싱하면 된다.

 

 

2. 자른문자열을 가지고 압축문자열을 만든다. --> 그 자른 단위들이 몇개가 있는지 어떻게 계산할 것인가?

 

이제 이렇게 각각의 자른 문자열 하나하나에 대해서 개수를 세야한다. (위의 포문 안에서 진행)

사실 여기에서 헤맸다.

처음에는 dict를 사용해서 count한 값을 넣으려고 했다.

그런데 생각해보니 이렇게 되면 단위문자가 key가 되서 압축값이 안된다.

예를 들어 aabbaaaaa일 경우 내가원한 압축개수는 1aa 1bb 3aa이여야하는데 key가 되는 바람에 4aa 1bb가 되더라.

 

그래서 직접 슬라이싱 한 문자열(tmp)과 비교해서 개수를 세도록 했다. 

현재 단위문자열(tmp)를 N개의 크기만큼 슬라이싱하도록 초기화한다. 

그리고 수행하게 될 포문은 이제 단위문자열의 다음문자부터 N개의 크기만큼 반복한다. 

예를들어, 2개단위로 자른다고 할 경우 i=2,4,6,8, 이며 N개의 크기만큼 건너뛰면서 문자열을 확인할 인덱스이다.

그래서 s[i:i+n]이 다음문자열부터 자를 단위문자열만큼 슬라이싱한 값이 된다. 즉 비교할 다음 단위문자열이다.

 

이제 현재단위문자열(tmp)와 다음문자열(s[i:i+n])이 같은지를 비교하면 개수를 셀수 있다.

같다면 갯수를 늘리고, 같지 않다면 처음으로 들어온 단위문자열이기 때문에 cnt는 1이 된다. 

그리고 다음비교를 위해 현재단위문자열(tmp)를 다음문자열로 이동한다. 

 

2-1.추가로 슬라이싱한 문자열의 개수가 1일때는 cnt가 생략된채 표현된다.

예를 들면 1aa1bb가 아니라 aabb인 것이다. 

그래서 cnt가1일때는 cnt 없이 문자열만 표현한다. 

반면에 여러번 들어온 문자열이라면 이제 최종적인 압축문자열(res)를 만들어준다. 

 

 

3. 마지막으로 길이가 가장 짧은것을 리턴한다.

처음엔 이 압축문자열을 다 구해서, length=[]라는 리스트에 다 넣고, 그 안에서 길이가 제일 짧은걸 가져오려고 했는데

굳이 그렇게 안해도 min()으로 할 수 있을 것 같다. 

결과

def solution(s):
    answer=10000
    for n in range(1,len(s)//2+1):
        res=''
        cnt=1
        tmp=s[:n] #단위문자열 초기화

        for i in range(n,len(s)+n,n):
            if tmp == s[i:i+n]:
                cnt+=1
            else:
                if cnt==1:
                    res+=tmp
                else:
                    res+=str(cnt)+tmp
                tmp=s[i:i+n]
                cnt=1
        #print(res)
        answer=min(answer,len(res))
    return answer

 

앗, 그런데 몇가지 테스트케이스가 통과되지 않았다.

찾아보니 처음에 절반의 길이까지 되는 경우는 s의 길이가 최소 2개일때였다. 

결국 s의 길이가 1일때는 고려하지 않게 되서 하나를 더 해줬다.

최종적으로 for n in range(1,len(s)//2+2): 로 추가변경했다. 

 

배운점

• 문자열을 슬라이싱을 적극활용하기
• 입력조건이1개 일때처럼 조건이 매우작을떄부터 매우 클 경우까지 극단적으로 생각해서 범위잡기 

---

참고 

참고한 블로그 링크

https://whwl.tistory.com/68

[프로그래머스] 문자열 압축/ 파이썬/ Python/ 2020 KAKAO BLIND RECRUITMENT/ 카카오 블라인드 채용

 

https://velog.io/@devjuun_s/%EB%AC%B8%EC%9E%90%EC%97%B4-%EC%95%95%EC%B6%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4python2020-Kakao-%EA%B3%B5%EC%B1%84