📗 문자열 압축

프로그래머스

def compress(s, n):
    result = ''
    cnt = 1
    prev = s[:n]
    
    for i in range(n, len(s), n):
        cur = s[i:i+n]
        if cur == prev:
            cnt += 1
        else:
            result += (str(cnt) + prev) if cnt > 1 else prev
            prev = cur
            cnt = 1
    result += (str(cnt) + prev) if cnt > 1 else prev
    
    return len(result)

def solution(s):
    answer = len(s)
    
    if answer == 1:
        return 1
    
    for n in range(1, len(s) // 2 + 1):
        comp_length = compress(s, n)
        answer = min(answer, comp_length)
    
    return answer

왜 이렇게 풀었을까?

필요한 사전 지식

• 문자열 슬라이싱하는 방법, 완전 탐색(브루트포스), 그리디, 슬라이딩 윈도우(까진 필요없을 수도)

이 문제로부터 구현력 기르기

• 문자열 s를 1개 이상의 단위로 자르는 방법을 고려해봤을 때,
• 단위 길이가 n일 경우 문자열을 앞에서부터 길이 n 단위로 나누고, 연속된 단위가 동일할 경우에 압축, 그리고 이 압축 결과를 하나의 새로운 문자열로 조합하는 방식을 택했습니다.
• 왜 함수로 따로 분리해서 구현했느냐?! 이유는 단위 길이 n에 따라 나와야하는 출력값이 다르기도 하고, answer를 지속해서 최솟값으로 업데이트 해줘야했기에 분리가 효율성을 높이는 하나의 방법이었습니다.
• 완전 탐색으로 진행했기에 최적해를 보장(그리디)할 수 있었고, 이 완전 탐색의 시간을 줄이기 위해 도입한 방법은 모두 탐색하는 것보다 문자열의 절반까지만 확인하는 것이었습니다.
  • 이유는 단위 길이가 len(s) // 2보다 크면 압축이 불가해서 의미가 없습니다!
• 구현하다보니 문자열의 특정 구간을 순차적으로 이동하며 비교하는 방식인 슬라이딩 윈도우가 적용된 것을 확인할 수 있었습니다.

이 문제로부터 연상력 기르기

• "문자열 압축"이라는 제목만 봐도 알 수 있듯, 문자열 문제임은 자명했습니다. 문자열의 구간을 나누어 차례차례 탐색하는 과정은 보통 슬라이싱 구간을 변화시켜주는 방식을 사용합니다.
• s의 길이가 1 이상 1000 이하입니다. 완전 탐색이 가능한 입력값이었습니다.
• 문제에 '가장 짧은', '가장 큰' 등의 수식어가 포함되어 있으면 보통 최적해를 찾는 그리디 구조라고 생각합니다. 이로 인해 최솟값을 업데이트 해주는 과정을 떠올렸습니다.
• 참고로 위 문제는 2020 KAKAO BLIND RECRUITMENT에 출제된 문제입니다.