[프로그래머스 / python / Level 2] 압축

문제

 

2018 KAKAO BLIND RECRUITMENT에 출제된 문제이다. 구현, 문자열 문제이고 문제 조건이 크게 어려운 건 아닌데, 구현 문제다 보니까 디테일한 부분에서의 실수가 없도록 주의해야 하는 문제이다.

 

def solution(msg):
    
    """인덱스 -> 문자열, 문자열 -> 인덱스 사전 제작"""
    idx_to_str = [''] + [chr(i) for i in range(ord('A'), ord('Z') + 1)]
    
    str_to_idx = dict()
    for i in range(26):
        char = chr(ord('A') + i)
        str_to_idx[char] = i + 1
        
    """메인 로직, 문자열을 전부 압축할 때 까지 반복"""
    result = []
    i = 0  # 시작 인덱스
    while i < len(msg):
        
        current = msg[i]
        
        # 범위를 1씩 늘려가며 가장 긴 문자열 추출
        j = i + 2
        while j <= len(msg) and msg[i:j] in str_to_idx:
            current = msg[i:j]
            j += 1
        
        # 결과에 인덱스 추가
        result.append(str_to_idx[current])
        
        # 다음 문자가 있다면 사전에 추가
        next_idx = i + len(current)
        if next_idx < len(msg):
            
            new_str = current + msg[next_idx]
            str_to_idx[new_str] = len(idx_to_str)
            idx_to_str.append(new_str)
        
        # 다음 시작 인덱스 갱신
        i = next_idx
    
    return result

 

우선 가장 먼저 사전2개를 제작한다. 인덱스로 문자열을 추출할 수 있는 리스트와, 문자열로 인덱스를 추출할 수 있는 딕셔너리. 미리 사전 2개를 만들어 두면, 메모리는 좀 더 먹겠지만 어떤 방식으로 조회하든 O(1) 시간에 조회할 수 있게 된다.

 

메인 로직은 단순하다. 시작, 끝(i, j) 범위를 정해놓고 끝 범위를 1씩 늘려가며 사전에서 해당 문자열이 존재하는지 찾으면 된다. 말했듯 조회 연산은 미리 만들어 둔 사전 덕에 O(1)이기 때문에 큰 부담이 없다. 그렇게 사전에 존재하는 가장 긴 문자열을 찾는다.

 

결과에 해당 문자열의 인덱스를 저장하고, 더 압축할 다음 문자가 존재한다면 저장한 문자열과 다음 문자를 합쳐 두 사전에 추가해 주면 된다.

 

가장 긴 문자열을 사전에서 찾고, 결과에 추가하고, 다음 문자와 합쳐서 사전에 저장. 이것을 반복하면 된다.