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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60057

풀이과정

2020 카카오 블라인드 채용 기출문제이다.
카카오는 문자열 문제가 많은 것 같다.
이번 문제는 알고리즘 분류를 하자면, 나는 '구현'으로 풀었다고 생각한다.
제한사항에서 문자열의 길이가 1이상 1000이하였기 때문에, 효율성 측면에서 깊이 생각하지 않았다.

그래서 1 ~ 문자열 길이//2 까지 완전 탐색하고 압축된 문자열 최솟값을 반환하는 방식으로 코드를 작성하였다.

이 문제에서 복병은 문자열의 길이가 1인 경우였는데, 런타임 에러로 한 테케만 실패가 떠서 금방 눈치챌 수 있었다.
하지만 만약에 테스트 케이스 어떤 것이 어떤 이유로 틀리는지 말해주지 않는 코테라면
나는 반례를 생각하지 못해서 틀렸을 확률이 높다.
항상 코드 제출 전에 반례를 생각해보자. 명심명심

코드

def solution(s):
    if len(s) == 1:
        return 1

    answer = float("inf")
    for n in range(1, len(s)//2+1):
        partial = s[0:n]
        tmp = ''
        cnt = 1
        idx = n
        while idx < len(s):
            if partial == s[idx:idx+n] :
                cnt += 1
                idx += n
            else:
                if cnt >= 2:
                    tmp = tmp + str(cnt) + partial
                else:
                    tmp += partial
                partial = s[idx:idx+n]
                idx += n
                cnt = 1
        if idx >= len(s):
            tmp = tmp + str(cnt) + partial if cnt >= 2 else tmp + partial
        answer = min(answer, len(tmp))
    return answer

s = "aabbaccc"
s = "ababcdcdababcdcd"
s = "abcabcdede"
s = "abcabcabcabcdededededede"
s = "xababcdcdababcdcd"
print(solution(s))

다른 사람의 풀이

def compress(s,length):
    target,s,cnt = s[:length], s[length:],1
    answer = ''
    while s:
        if target==s[:length]:
            s,cnt = s[length:], cnt+1
        else:
            answer+=str(cnt)+target if cnt>1 else target
            target,s,cnt = s[:length], s[length:], 1
    return len(answer+str(cnt)+target if cnt>1 else answer+target)
def solution(s):
    answer = len(s)
    for i in range(1,len(s)+1):
        answer = min(answer,compress(s,i))
    return answer

이번에는 특별히 눈에 띄는 놀라운 코드가 없었다.
이 코드는 압축하는 함수를 따로 빼서 깔끔하게 작성한 점이 마음에 든다.