프로그래머스 문자열 압축 코드 및 해설 (파이썬)

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

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

 

💡 1부터 문자열 s의 길이까지 1씩 증가하며 각 단위로 잘라 압축해보고, 이 중 최단 길이를 반환하도록 했습니다.

 

문자열 압축은 우선 빈 string인 result를 만들어주고 단위에 따라 문자열을 잘랐습니다. 자른 문자열이 이전에 자른 문자열과 같으면 문자열 뒤의 count만 하나씩 늘려주고, 다르면 현재 문자열을 result에 append 한 뒤 count를 1로 주었습니다. 마지막에 count가 1인 부분은 지워 최종 압축된 문자열을 반환했습니다.

 

count를 하나씩 늘려줄 때, 자릿수 때문에 오류가 났는데, count가 항상 일의 자릿수에 머무는 게 아니라는 것을 주의하며 풀이해야 합니다. 저는 정확한 자릿수를 파악하기 위해 while문을 사용했습니다.

 

• 문제에 주어진 방식과 숫자랑 문자열의 순서가 반대인데, 최단 길이를 구하는 것이라 크게 상관없을 것 같아 그대로 했습니다

 

import re 

def ngram(s, n):
    result = ''
    prev = ''
    
    for i in range(0,len(s),n):
        cur = s[i:i+n]
        # 이전과 같다면 count 하나씩 올려주기 
        if prev == cur:
            idx = -1
            # 마지막 숫자의 자릿수 확인 
            while len(result) > -idx and result[idx].isdigit():
                idx -= 1 
            result =  result[:idx+1] + str(int(result[idx+1:]) + 1)
        # 이전과 다르다면 현재 ngram과 빈도 1을 더해주기 
        else:
            result += cur + '1' 
        # 이전 ngram을 현재의 것으로 업데이트 
        prev = cur
    
    # 맨 마지막 ngram 빈도가 1인 경우, 1 지우기 
    if result[-2].isalpha() and result[-1] == '1':
        result = result[:-1]
    # 알파벳 사이에 있는 1은 모두 지우기 
    return re.sub('(?<=[a-z])1(?=[a-z])', '', result) 


def solution(s):
    length = len(s)
    min_length = length
    
    # 각 i개 단위로 잘라 압축했을 때, 최단 길이 반환하기 
    for i in range(1, length):
        cur_length = len(ngram(s, i))
        if min_length > cur_length:
            min_length = cur_length
    
    return min_length

 

 

++ 자릿수를 알아내기 위한 while을 삭제하고 자릿수를 저장하는 digit 변수를 도입

 

def ngram(s, n):
    result = ''
    prev = ''
    digit = 0 

    for i in range(0,len(s),n):
        cur = s[i:i+n]
        # 이전과 같다면 count 하나씩 올려주기 
        if prev == cur:
            count = int(result[-digit:])
            result =  result[:-digit] + str(count + 1)
            #9, 99, 999,...이면 자릿수 1 증가 
            if set(str(count)) == {'9'}:
                digit += 1 
        # 이전과 다르다면 현재 ngram과 빈도 1을 더해주기 
        else:
            # 직전의 ngram 빈도가 1인 경우, 1 지우기 
            if digit == 1 and result.endswith('1'):
                result = result[:-1]
            result += cur + '1' 
            digit = 1 
        # 이전 ngram을 현재의 것으로 업데이트 
        prev = cur

    # 마지막 ngram 빈도가 1인 경우, 1 지우기
    if digit == 1 and result.endswith('1'):
        result = result[:-1]
    return result


def solution(s):
    length = len(s)
    min_length = length

    # 각 i개 단위로 잘라 압축했을 때, 최단 길이 반환하기 
    for i in range(1, length):
        cur_length = len(ngram(s, i))
        if min_length > cur_length:
            min_length = cur_length

    return min_length