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

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

프로그래머스

문제

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 비손실 압축방법을 표현하자

 

제한 사항

• S의 길이는 1이상 1000이하
• S는 알파벳 소문자로만 이루어져있다.

입출력 예시

sresult

"aabbaccc"	7
"ababcdcdababcdcd"	9
"abcabcdede"	8
"abcabcabcabcdededededede"	14
"xababcdcdababcdcd"	17

 

해결 방법

구현문제이다. 중복되는 단어의 갯수를 1부터 len(s)/2까지 설정해가며 중복된 단어를 찾아 축소하고 짧은 문자열의 최솟값을 찾는다. 

 

코드

def solution(s):
    answer=len(s)
    #스텝 설정
    for step in range(1, len(s)//2 +1) :
    	#압축 문자열 저장할 변수 초기화
        compressed=""
        #앞에서부터 step만큼 문자열 추출
        prev=s[0:step]
        #중복갯수 1로 초기화
        count=1
        for j in range(step, len(s), step) :
        	#step만큼 크기 증가시키며 이전 문자열과 비교
            #이전 상태와 동일하다면 count 1 추가
            if prev==s[j:j+step] :
                count+=1
            else :
            	#count가 2보다 크다면 앞에 카운트와 이전 상태 compressed에 추가, 2보다 작다면 그냥 이전 상태 추가
                compressed+=str(count)+prev if count>=2 else prev
                #다시 상태 초기화
                prev=s[j:j+step]
                count=1
        #남아있는 문자열에 대해서 처리
        compressed+=str(count)+prev if count>=2 else prev
        #만들어진 압축 문자열이 가장 짧은 것이 정답
        answer=min(answer, len(compressed))
    return answer

※<이것은 취업을 위한 코딩테스트다 (나동빈저)>를 참고하여 작성하였습니다.