문자열 압축 (Level 2)

문제

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

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

 

내 풀이

1. 문자열을 cut만큼 잘라서 words에 담았다.
2. cnt_list를 만들었는데, words를 돌면서 [현재 문자 == 전의 문자]이면 현재 문자의 인덱스에 해당하는 cnt_list 원소에 숫자를 증가시켰고, 전의 문자 인덱스 원소를 0으로 만들었다. 0으로 만든 이유는 압축 과정에서 0이면 제외시키기 위함이다. 길이가 1인 문자를 위해 cnt_list를 1로 초기화하였다.
3. cnt_list를 돌면서 숫자가 1 이상인 경우만 길이를 체크해주었다. 

 

import math

def solution(s):
    answer = math.inf
    for cut in range(1, len(s)+1):
        length = 0
        words = []
        for i in range(0, len(s), cut):
            words.append(s[i:i+cut])
            
        cnt_list = [1]*len(words)
        for i in range(1, len(words)):
            if words[i] == words[i-1]:
                cnt_list[i] = cnt_list[i-1] + 1
                cnt_list[i-1] = 0
        for i, cnt in enumerate(cnt_list):
            if cnt == 1:
                length += len(words[i])
            elif cnt > 1:
                length += len(words[i]) + len(str(cnt))
        answer = min(answer, length)
    return answer

 

다른 풀이

1. 리스트에 for문을 넣는 방식을 채택하여 코드 라인 수를 줄였다.
2. cur_word와 cur_cnt를 이용하여 문자 하나하나 비교하는 방식을 썼다. 이 알고리즘은 코드 저자의 머리에서 나온 알고리즘이라, 외우지 않는 한 내 머릿속에서 빠르게 나오기 힘들 것 같다.  
3. 문자열을 전체 다 보지 않고, len(text)/2 길이만큼 확인하였다. 반만 확인해도 가능하다. 이로써 효율성을 높일 수 있다. (눈여겨보기!!!)

 

def compress(text, tok_len):
    words = [text[i:i+tok_len] for i in range(0, len(text), tok_len)]
    res = []
    cur_word = words[0]
    cur_cnt = 1
    for a, b in zip(words, words[1:] + ['']):
        if a == b:
            cur_cnt += 1
        else:
            res.append([cur_word, cur_cnt])
            cur_word = b
            cur_cnt = 1
    return sum(len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)

def solution(text):
    return min(compress(text, tok_len) for tok_len in list(range(1, int(len(text)/2) + 1)) + [len(text)])

 

총평

파이토닉 하게 짤 수 있는 코드는 파이토닉 하게 짜기!