[알고리즘] 프로그래머스 - 문자열 압축

프로그래머스 - 2020 KAKAO BLIND RECRUITMENT 문자열 압축

내 풀이

'''
Problem Solving Programmers 60057
Author: Injun Son
Date: February 23, 2021
'''
import sys
import collections
import heapq
import functools
import itertools
import re
import math
import bisect


def compress_string(answer, length, s):
    words = cut_string(length, s)

    words = words + ["Z"]
    prev =  "A"
    count = 0
    tmp_string = ""
    for word in words:
        if word == prev:
            count += 1
        else:
            if count > 1:
                tmp_string += str(count) + prev
            else:
                tmp_string += prev
            count = 1
            prev = word

    answer.append(tmp_string[1:])


def cut_string(length, s):
    words = []
    prev = 0
    while prev + length < len(s):
        words.append(s[prev: prev + length])
        prev += length
    if prev < len(s):
        words.append(s[prev:])
    return words

def solution(s):
    answer = []
    for i in range(1, len(s)+1):
        compress_string(answer, i, s)

    # print(answer)
    return min(len(x) for x in answer)

print(solution("aabbaccc"), 7)
print(solution("ababcdcdababcdcd"), 9)
print(solution("abcabcdede"), 8)
print(solution("abcabcabcabcdededededede"), 14)
print(solution("xababcdcdababcdcd"), 17)
print()
print(solution("aababa"), 5)
print(solution("aaaaaaaaaab"), 4)

문자열을 하나씩 자를지, 두개씩 자를지 완전탐색을 한다. cut_string함수는 몇 개씩 자를지 매개변수로 받아서 list로 돌려주는 함수이다. index error가 발생하지 않게 마지막 전에 미리 끝내고, 남아있으면 남은거를 더해주는 방식이다.

compress_string 함수는 압축해주는 함수인데 예를 들어 ['a', 'a', 'b', 'b', 'a', 'c', 'c', 'c'] 이렇게 있으면 '2a2ba3c' 로 압축해준다. 예전 네이버 부스트캠프에도 이런 중복되는 것을 카운팅하는 문제가 나왔는데, 리스트에 절대 들어 올 수 없는 문자를 뒤에 붙여주는 방식이 괜찮은 것 같다. (여기서는 소문자만 들어오므로 앞 뒤에 대문자를 붙여줬다). prev에는 절대 올 수 없는 문자인 "A"를 붙여줬는데, 이는 실제 string의 첫 문자를 만나면 바로 리뉴얼 될 것이다. 그리고 이 부분은 마지막에 return 할 때 제거하면된다. 마지막에 Z를 붙인 것은, 그렇지 않았을 때 "ccc"부분에서 count만 올라가고 string에 붙여지지 않고 끝날 수 있기 때문에 강제로 항상 끝을 내주기 위해서이다.

처음에 틀렸는데, 틀린 이유가 aaaaaaaaaab=> 10ab => 4 같은 경우를 고려하지 못했는데, int형을 str으로 바꿀 때는 항상 조심해야한다.

cut_string 함수를 파이써닉하게 대체할 수 있다.

[s[i:i+length] for i in range(0, len(s), length)]

끝 인덱스를 초과하면 에러가 난다고 생각했는데 슬라이싱은 끝 인덱스를 초과해도 괜찮다.

a = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]
print(a[0:20])    # 인덱스 0부터 9까지 잘라서 새 리스트를 만듦

출력 결과: [0, 10, 20, 30, 40, 50, 60, 70, 80, 90]

간단해진 코드

def compress_string(answer, length, s):
    words = [s[i:i+length] for i in range(0, len(s), length)]
    words = words + ["Z"]
    prev = "A"
    count = 0
    tmp_string = ""
    for word in words:
        if word == prev:
            count += 1
        else:
            if count > 1:
                tmp_string += str(count) + prev
            else:
                tmp_string += prev
            count = 1
            prev = word

    answer.append(tmp_string[1:])

def solution(s):
    answer = []
    for i in range(1, len(s)+1):
        compress_string(answer, i, s)

    return min(len(x) for x in answer)

유사한 문제

유사문제 "짝지어 제거하기"

가장 긴 팰린드롬 - 단위쪼개서 확인하는 흐름 유사