프로그래머스 - 문자열 압축

문자열 압축

설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

def getDivisor(n):

    divisorsList = []

    for i in range(1, n + 1):
        if (n % i == 0) :
            divisorsList.append(i)

    return divisorsList
# 에잇 약수로 안나눠떨어져도 됨
# 남는건 그냥 이어 붙이기

• 문제를 똑바로 읽자

    for i in range(1, length+1):
        tmp = s[:]
        cnt = 0
        token = s[:i]
        while tmp:
            if tmp.startswith(token):
                tmp = tmp[i:]
                cnt += 1

• 처음 생각한건 토큰을 계속 잘라가며 startswith를 활용하는 방법이다.
• 근데 토큰을 계속해서 나누고 비교하고 하려면 반복문이 많이 중첩될 것 같아서 일단 보류

def solution(s):
    answer = 1001
    length = len(s)
    dic = {}
    keylist = []
    
    if length == 1:
        return length
    
    
    for i in range(1, length):
        keylist = []
        compress = ''
        k = 0
        while k+i < length:
            keylist.append(s[k:k+i])
            k = k+i
        keylist.append(s[k:])
        keylist.append('')
        
        prev = keylist[0]
        cnt = 1
        for j in range(1, len(keylist)):
            if keylist[j] == prev:
                cnt += 1
            else:
                if cnt == 1:
                    compress += '*'
                else:
                    compress += str(cnt)
                compress += prev
                prev = keylist[j]
                cnt = 1
        compress = compress.replace('*','')
        # 이거를 그냥 1->'' 하면 10, 112 이런거에서 틀림
        # 1을 안쓰는 문자로 바꾸고 교체하자
        # print(compress)
        curLen = len(compress)
        if curLen < answer:
            answer = curLen

    
    # print(answer)
    return answer

• 다음으로 생각한 방식은 1부터 단어의 길이까지 늘려가며 단어를 전부 잘라내는 것이다.
• 전부 잘라낸 뒤, 이전의 토큰과 같다면 카운트하고, 다르면 이전까지 카운트한 갯수에 이전 토큰을 이어붙혀 정답 문자열을 생성한다.
• 그 중 길이가 가장 짧은 문자열을 정답으로 리턴
• 여기서 중요한 점 하나는 1은 표시를 안하기 때문에, 처음엔 1을 ''로 교체했는데 그러면 10이나 112 등 1이 들어가는 큰 자릿수 숫자도 바뀌어 버린다.
• 그래서 카운트가 1이면 안쓰는 문자로 치환해서 넣어주고 한번에 지워주면 된다.