프로그래머스: [3차] 압축 (파이썬, 구현)

간단한 구현 문제이나 푸는데는 30분정도 걸린 것 같다.. 대기업 코딩 테스트에는 구현 문제가 한 두문제씩 나오는 경우가 많아 여러가지 케이스들을 미리 해보는게 빠른 구현에 도움이 될 것 같다.

 

문제를 살펴보면 주어진 문자열을 LZW라는 알고리즘으로 압축을 해야 하는데 이 알고리즘은 사전의 인덱스를 이용하여 해당하는 문자의 인덱스를 출력하는 방식이다.

 

따라서 문제를 풀기 위해서는 우선 대문자들로 dictionary를 미리 초기화 시켜야함을 알 수 있다. 그 후 반복문을 이중중첩하여 문자열을 탐색하는데 내부의 반복문은 dictionary가 계속 늘어나기에 그에 맞춰 문자열을 dictionary의 key에 없을때까지 더하는 용도이다.

 

from string import ascii_uppercase


def solution(msg):
    answer = []
    dic = {}
    # dictionary 생성, 나중에 dictionary에 새로운 변수들을 저장하기 위해서 마지막 인덱스를 변수에 저장.
    last_i = 0
    for i, alphabet in enumerate(list(ascii_uppercase)):
        dic[alphabet] = i + 1
        last_i = i + 1
    # 인덱스가 불규칙하게 바뀌므로 while문 사용
    m = 0
    while m < len(msg):
        keys = list(dic.keys())
        cash = msg[m]
        index = m + 1
        while index < len(msg):
            # 시작문자열 + 다음문자열이 dictionary의 key들에 없을때까지 문자열 더함
            if cash + msg[index] in keys:
                cash += msg[index]
                index += 1
            else:
                break
        answer.append(dic[cash])
        # 22줄에서 index에 1을 더하기에 index가 문자열의 마지막 인덱스보다 커지는 것 방지
        if index < len(msg):
            dic[cash + msg[index]] = last_i + 1
            last_i += 1
        m = index
    return answer