코딩/프로그래머스 lv2

[프로그래머스] 문자열 압축 - python

코딩 코딩 코오딩 2021. 5. 2. 01:18

<문제>

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

 

코딩테스트 연습 - 문자열 압축

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문

programmers.co.kr

 

<시간 복잡도>

 

<코드>

def solution(s):
    length = []
    result = ""

    if len(s) == 1:
        return 1

    for cut in range(1,len(s)//2+1):
        count =1
        tempstr=s[:cut]
        for i in range(cut,len(s),cut):
            if tempstr==s[i:i+cut]:
                count+=1
            else:
                if count ==1:
                    count =''
                result += str(count)+tempstr
                count=1
                tempstr=s[i:i+cut]
        
        if count ==1:
            count =''
        result += str(count)+ tempstr
        length.append(len(result))
        result =''


    return min(length)

<해설>

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

 

문자열 압축-프로그래머스(python)(2020 Kakao 공채)

문제링크 : 문자열 압축 - 프로그래머스 https://programmers.co.kr/learn/courses/30/lessons/60057데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량

velog.io

 

참고해서 푼 블로그이다.

 

우선 이 문제의 핵심은 계속해서 일치하는 문자열을 찾아내는 것이다. 완전 탐색? 이랑 비슷하다고 생각한다.

 

여기서 핵심 아이디어는

 for cut in range(1,len(s)//2+1):
        count =1
        tempstr=s[:cut]
        for i in range(cut,len(s),cut):
            if tempstr==s[i:i+cut]:
                count+=1
            else:
                if count ==1:
                    count =''
                result += str(count)+tempstr
                count=1
                tempstr=s[i:i+cut]

이 부분이라고 생각한다, 특히 for 문의 사용법이 나는 정말 많은 것을 배웠다.

가장 바깥에 있는 for문은 무엇을 의미할까?

가장 바깥에 있는 for문에서 구하는 것은 

 tempstr=s[:cut] 이다 이것의 의미는 초기 문자열을 지정해주는 역할을 한다.

안에 있는 for문에서 이제 핵심적으로 반복해가며 겹쳐지는 문자열을 찾는 역할을 한다.

cut의 수를 조금씩 늘려가며 해준다고 생각하면 된다.

2로 나누는 행위를 하는 것은 굳이 더 넓은 범위의 배열까지 구할 필요가 없기 때문이다. cut의 수가 커지므로..

이렇게 구한 for문 밖으로 나오게 되면 한번더 마무리 되는 문자열에대하여

 

if count ==1:
    count =''
result += str(count)+ tempstr
length.append(len(result))
result =''

이렇게 해줌으로써 마지막 문자열까지 추가해줄 수 있다. 

마지막에 반복해준 문장은 추가적으로 해줘야 하기 때문이다.

반응형