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

이다혜·2021년 5월 4일
0

Lv2. 문자열 압축

문제

압축할 문자열 s가 매개변수로 주어질 때, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

  • 입출력 예시
입력압축된 문자열출력
"aabbaccc""2a2ba3c"7
"ababcdcdababcdcd""2ababcdcd"9
  • 제한사항
    - s의 길이는 1 이상 1,000 이하입니다.
    - s는 알파벳 소문자로만 이루어져 있습니다.

나의 풀이

# 문자열 text와 자를 단위 num을 받아서 압축된 문자열의 길이 반환 
def compress(text, num):
    compressed = ''
    n = len(text)
    length = n // num * num  # 각 단위로 잘랐을때 고려해야할 문자열 길이
    end = length - (2 * num)
    cnt = 1 # 문자열이 반복되는 횟수를 저장
    
    for i in range(0, end + 1, num):
        # num 단위로 문자열이 같은지 검사
        if text[i:i + num] == text[i + num:i + 2 * num]:
            cnt += 1
            # 마지막 단위일 경우
            if i == end:
                compressed += str(cnt) + text[i:i + num]
        else:
            if cnt == 1: cnt = ''
            compressed += str(cnt) + text[i:i + num] # 압축된 문자열 업데이트
            cnt = 1 # 횟수 초기화
            # 마지막 단위일 경우
            if i == end:
                compressed += text[i + num:i + 2 * num]
    
    # 남는 문자열을 더함
    compressed += text[length:]
    return len(compressed)

def solution(s):
    answer = []
    if len(s) == 1:
        return 1
    # 1부터 len(s)의 절반 단위까지 num을 늘려가면서 압축해본다
    else:
        return min([compress(s, num) for num in range(1, len(s) // 2 + 1)])

상위 풀이

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)])
profile
하루하루 성장중

0개의 댓글