[이코테] Implementation _ 문자열 압축

9. 문자열 압축

🏃‍♀️ 문제 분석

• 압축된 문자열 중 가장 짧은 문자열을 만들 것!
  • 1 <= s <= 1000
  • s는 소문자로만 이루어짐
  • 문자열 단위는 길어져도 됨!

🗝내 답안

# 코드 정리된 버전
def solution(s):
    res = []
    if len(s) < 2: return len(s)
    for zip_len in range(1,len(s)//2+1):
        cnt = 0 # 패턴 개수
        check = 0 
        ch_cnt = 0 # 자리 수 체크
        diff = 0 # 패턴이 아닌 다른 문자 조각들 체크
        extra = 0
        pattern_prev = 0
        pattern_init = s[:zip_len]
        for i in range(zip_len, len(s)+1, zip_len):
            compare = s[i:i+zip_len]
            if len(compare) < zip_len:
                extra += len(compare)
                break
            if pattern_init == compare:
                check+=1
                if pattern_prev != pattern_init:
                    pattern_prev = pattern_init
                    check+=1
                    cnt+=1
                    diff-=1
            else:
                diff+=1
                pattern_prev = pattern_init
                pattern_init = compare
                ch_cnt += len(str(check)) if check > 1 else 0
                check = 0

        ch_cnt += len(str(check)) if check > 1 else 0
        res.append((diff+1)*zip_len + (cnt*zip_len + extra +ch_cnt))
    return min(res)

🛠 이코테 답안

sentence = input()
length = len(sentence)
answer = len(sentence)

# 단위가 될 수 있는 경우
for unit in range(1, length//2+1):
    compressed = ""
    prev = sentence[0:unit]
    count = 1  # 동일한 탐색 단위의 개수
    for j in range(unit, length, unit):
        # compressed
        if prev == sentence[j:j+unit]:
            count += 1
        else:
            compressed += str(count) + prev if count >= 2 else prev
            prev = sentence[j:j+unit]
            count = 1
            
    compressed += str(count) + prev if count >= 2 else prev # 남아있는 문자열에 대해 처리
    # 탐색 단위별로 압축 문자열의 길이를 비교해, 최소 압축 문자열의 길이를 저장
    answer = min(answer, len(compressed))
print(compressed)
print(answer)

🔐 정답 분석

📌 기억할것!

• 탐색 데이터가 1000이하 -> 완전 탐색 가능
• 테스트케이스 고려하기!
  • 내 풀이에서 막혔던 부분
    • 반복되는 문자열이 2종류인데, 하나는 10개가 넘어가고 하나는 안 넘어가는 경우에 문제가 생겼음
    • 패턴 별로 따로 세고, 문자열로 변경하여 자릿 수를 더해주는 방식으로 해결!