파이썬 문자열 압축(feat. 프로그래머스 문자열 압축 문제)

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

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

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 s[i:i+cut] == tempStr:
                count += 1
            else:
                if count == 1:
                    count = ""
                result += str(count) + tempStr
                tempStr = s[i:i+cut]
                count = 1
        if count == 1:
            count = ""
        result += str(count) + tempStr
        length.append(len(result))
        result = ""
    return min(length)

 

2020 카카오 블라인드 채용 문제에 올라온 문제이다.

문자열을 처음부터 N개까지 압축하고, 압축한 문자열 중 가장 짧은 문자열의 길이를 return하는 문제이다.

 

알고리즘

1. 만약 input된 문자열의 길이가 1이라면 1을 return한다.

2. 자를 길이를 1부터 (문자열 길이 나누기 2한 몫) + 1까지 for문을 돌린다.(절반 이상까지 자르는 것은 무의미하다.)

3. count = 1로 초기화하고, 임시저장 str을 처음부터 자를 길이까지 잘라 저장한다.

4. for i in range(cut,len(s), cut) => range의 3번째 항에 cut을 넣으면 자를 단위 만큼 건너뛰며 for문을 돈다.

5. tempStr에 저장한 이후의 문자열이 cut 단위로 자른 문자 s[i:i+cut] 와 같다면 count에 1을 더해준다.

6. 같지 않고 count == 1이라면 count ="" 로 셋팅하고, count !=1이라면 result = result + str(count) + tempStr을 해준다.

7. 다시 tempStr에 s[i:i+cut] 을 저장하고( s[i:i+cut]이 이전 tempStr과 달랐기 때문에 현재 tempStr로 셋팅), count =1로 초기화 한다.

8. Length 중 최소값을 return한다.