[프로그래머스] 문자열 압축 in Python

문제 풀러 가기

느낀점

전 사실 이 문제 어떻게 풀었는지 잘 모르겠습니다. 예전에 알고리즘을 처음 배울 때인 21년 2월 정도에, 겁도 없이 이 문제에 접근했다가 새벽까지 잠을 못자게 했던 기억이 있었습니다. 그리고 그냥 생각했어요. 아... 난 아직 이런 문제 못푸는구나..ㅜㅜ 그래서 해설도 보고 그랬는데, 못풀겠드라구요. 그게 바로 반년 전 정도였습니다. 그래서 이 문제를 풀 생각을 접고 있었습니다. 뭔가 레벨 2문제인데, 잘 모르겠다.. 이런 생각 말고는 안드니까. 풀기가 그렇더군요. 근데 사람이라는게 이번에는 혹시? 하면서 다시 이 문제를 들여다봤습니다. 물론 옆에는 빈 종이를 들고 차근차근 규칙을 찾았습니다. 다행히 규칙을 찾으니까 코드를 입력하는데 드는 시간은 얼마 안걸렸어요. 그리고 문자열의 길이가 1이 나오는 엣지케이스는 추후에 코드를 더하는 식으로 짰습니다. 그리고 다행히 풀었습니다. 풀어서 너무 기분이 좋았습니다ㅜㅜ

해설

이문제의 문자열의 구간을 문제의 조건대로 나눌 수 있는가? 인데요.
공책에 적으면서 하니까. 그 규칙이 바로 보여서 코드로 옮기는건 오래 걸리진 않았습니다.

파이썬 기준으로 문자열 slicing하면 인덱스가 다음과 같아요.

1개로 나눌 때는
(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), ...

2개로 나눌 때는
(0, 2), (2, 4), (4, 6), (6, 8), (8, 10), ...

3개는 안적어도 되겠죠?

어차피 문자열 slice는 전체 문자열의 반만 하면 되니까. 1000개를 다 순회할 필요는 없지요. 그래서 전체 문자열의 개수 중 반만 순회합니다. 그렇기 때문에 2중 순회는 필수적입니다. 2중 for문을 쓰면 최악의 시간 복잡도가 500 * 1000 = 500,000 이네요. 최대 50만의 순회로 모든 것을 다 탐색할 수 있습니다. 완전 탐색이 가능하다는 것이죠.

반복문 내부에 연속해서 나타났다는 것을 알기 위해 하나의 리스트와 숫자를 만듭니다. 그리고 리스트에 슬라이스한 문자를 넣어주면서 마지막 문자와 이제막 자른 문자열이 같다면, 일단은 리스트에 넣지는 말고 숫자를 증가시켜줍니다. 그리고 만약에 리스트이 마지막 인덱스와 지금 막 뽑은 문자열이 다르다면, 지금까지 모았던 숫자가 1이 아닌 경우에만 리스트의 마지막 인덱스만 수정해주고 방금 뽑은 문자열도 넣어줍니다. 만약에 숫자가 1이라면 그냥 넣어주면 됩니다. 그리고 간격 별로 순회가 끝날 때 마다 문자열의 갯수를 세서 정답을 업데이트 해줍니다.

아래는 코드에요.

def solution(s):

    s_len = len(s)

    if s_len == 1:
        return 1

    ans = 10000

    for i in range(1, (s_len//2)+1):
        string = []
        num = 1

        for j in range(0, s_len, i):
            if not string:
                string.append(s[j:j+i])
                continue

            if s[j:j+i] == string[-1]:
                num += 1
            else:
                if num == 1:
                    string.append(s[j:j+i])
                    continue

                string[-1] = str(num) + string[-1]
                string.append(s[j:j+i])
                num = 1

        if num == 1:
            if ans > len("".join(string)):
                ans = len("".join(string))
            continue

        string[-1] = str(num) + string[-1]
        if ans > len("".join(string)):
            ans = len("".join(string))
    return ans

솔직히 말씀드려서 있는 그대로를 생각없이 코드로 옮긴 것이기 때문에 제 코드는 좋다고 볼 수는 없습니다. 그래도 일단 풀었다는게 너무 기분 좋네요.
오늘은 여기까지!