[카카오 2020 코테 #1] 문자열 압축 - python

처음에 입출력 예 #5 를 보지 못해서

'문자열이 제일 앞부터 정해진 길이만큼 잘라야'한다는 점을 몰랐다

 

그래서 더 어렵게 생각하다보니 문제 난이도에 비해서 생각을 매우 오래했던 문제다

항상...! 문제를 잘 읽어보고 문제에 임하도록하쟈!

 

로직

살짝 brute force(전체 탐색)느낌이다

chunking 단위를 len(s)//2 부터 1까지로 잡고

 

[ 반복 ] chunking 단위 > 0 일 동안

  [ 반복 ] 문자열을 chunking 단위만큼 잘라준다

    앞의 문자열과 같으면 카운트해주고

    같지 않으면 카운트를 멈추고 압축가능한 경우 압축한다.

  chunking 길이를 -1

코드

1차 코드

def solution(s):
    answer = len(s)
    total_len = len(s)
    string_len = len(s)//2
    
    while string_len > 0:
        new_string, prev, count, i = "", "", 0, 0
        while i < total_len:
            next_chunk = s[i:i+string_len]
            
            if prev != next_chunk:
                comp = str(count) if count > 1 else ""
                new_string += (comp + prev)
                count = 0
            prev = next_chunk
            count+=1
            i += string_len
            
        comp = str(count) if count > 1 else ""
        new_string += (comp + prev)
        string_len -=1
        if len(new_string) < answer: answer = len(new_string)
    return answer

 

좀 더 깔끔하게 코드를 만들어 봤다

 

def solution(s):
    answer = len(s)
    string_len = len(s)//2
    
    while string_len > 0:
        comp, count = 0, 1
        prev = s[:string_len]
        for i in range(string_len, len(s)+string_len, string_len):
            next_chunk = s[i:i+string_len]
            
            if prev != next_chunk:
                comp += (string_len + len(str(count))) if count > 1 else len(prev)
                prev = next_chunk
                count = 0
            count +=1
        string_len -=1
        answer = min(answer, comp)
        
    return answer

 

 

가장 큰 차이는

 

1. 내부 while을 for 문으로 수정

  - 불필요한 초기 변수 선언X (i 초기 선언, i 값 업데이트)

2. new_string으로 압축된 문장(string)을 저장하는 대신 comp에 지금까지 압축되어 나온 문자의 길이(int)만 저장

  - 불필요한 초기 변수 선언X (new_string 필요 X)

  - 문자열을 자르고 붙이고 할 때 드는 time complexity가 분명히 있었을 텐데, comp에서 문자의 길이만으로 관리하여 불필요한 연산을 줄일 수 있음

3. 완성된 comp와 answer 중 더 작은 값을 선택할 때 min()을 사용

  - 가독성이 훨씬 좋아졌다