[이코테] 구현_문자열 압축 (python) (다시 풀어보기)

문제

나의 풀이

1. 일일히 비교하기.. pythonic 하지 않다ㅠ: 성공

def solution(s):
    answer = [] # 잘라낸 길이에 따른 문자열 개수를 담을 list 초기화
    
    # 1개 ~ s의 길이만큼 잘라냄
    for i in range(1, len(s) + 1):
    	# 중복 개수, i개 단위로 잘라낼 문자열, 압축한 문자열을 담을 것
        s_count, s_slicing, result = 1, '', ''
        
        start = 0 # 잘라내기 시작할 index
        end = start + i # 끝 index
        
		how_many = len(s) // i + 1 if len(s) % i == 0 else len(s) // i + 2
        
        # s의 길이는 i개 단위로 몇번 셀 수 있나
        for j in range(how_many):
            if s_slicing == s[start:end]: # 기준과 같은 문자열일 때
                s_count += 1 # 중복 개수 증가
            else:
				# result 갱신
				result += str(s_count) + s_slicing if s_count > 1 else s_slicing
				# 중복 개수 초기화, 기준 문자열 갱신
                s_count, s_slicing = 1, s[start:end]
                
            start += i # 시작 index 갱신
            end = start + i # 끝 index 갱신
            
        answer.append(len(result))     
        
    return min(answer) # 경우의 수중 가장 짧은 길이는?

: pythonic 하지 않다..!
for과 if의 범벅이라니ㅠ 넘나 부끄럽..

• 가장 시간 복잡도가 큰 케이스
  : 테스트 20 〉 통과 (5.85ms, 10.2MB)

2. 성공: 역시나 일일히 비교

# 새로 만든 문자열 저장 함수
def result_save(result, num, before):
    if num >= 2: # 단위가 반복된 횟수가 2번 이상일 때
        result += str(num) + before
    else:
        result += before
    return result, num, before

def solution(s):
    len_s = len(s)
    answer = len_s # 길이 초기화
    # 단위의 길이는 1 ~ 문자열의 절반까지 살펴봄
    unit_len = list(range(1, len_s // 2 + 1))
    for unit in unit_len:
        std = s[:unit] # 비교에 쓰일 단위
        before = s[:unit] # 단위와 다를때 초기화
        diff_true = False # 단위와 다른가? 초기화
        num = 1 # 단위와 같은 횟수
        result = '' # 최종 결과물 초기화
        
        for u in range(unit, len_s, unit): # 단위만큼 건너뛰면서 살핀다
            now = s[u:u+unit]
            if std == now: # 단위와 같다면
                before = now # 저장용 문자열 저장
                num += 1
                diff_true = False
                
            else: # 단위와 다르다면
                result, num, diff = result_save(result, num, before)
                std, before = now, now # 단위와 저장용 문자열 재지정
                num = 1
                diff_true = True
        # 미처 추가하지 못한 문자열 저장        
        result, num, diff = result_save(result, num, before)
        answer = min(answer, len(result)) # 가장 짧은 길이로 갱신
        
    return(answer)

• 가장 시간 복잡도가 큰 케이스
  테스트 26 〉 통과 (5.02ms, 10.2MB)

다른 사람 풀이(프로그래머스)

1. pythonic!

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)])

a = [
    "aabbaccc",
    "ababcdcdababcdcd",
    "abcabcdede",
    "abcabcabcabcdededededede",
    "xababcdcdababcdcd",

    'aaaaaa',
]

for x in a:
    print(solution(x))