문제

문제 링크

코드

from collections import deque
dp: dict

def solution(msg):
    global dp
    answer = []
    
    # 1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
    dp = dict()
    cnt = 1
    for c in list("ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
        dp[c] = cnt
        cnt += 1
    
    q = deque(msg)
    
    while q:
        now = q.popleft()
        while q and now + q[0] in dp.keys():
            now += q.popleft()
        w = now
        answer.append(dp[w])
        if q:
            c = q[0]
            dp[w+c] = cnt
            cnt += 1
        
    return answer

깨달은 점

순차적으로 데이터를 처리해야 할 때, 
조건에 따라 처리해야 하는 데이터가 추가되어
조건이 충족된 임의의 크기의 데이터를 처리할 때는 큐를 사용하자.

처음에는 투포인터로 풀려고 했다.
그 접근은 투포인터로 문자를 순회할 때 종결 조건을 생각해내기 어려웠다.
즉, 사용하려는 자료구조가 잘못된 경우에 많은 오버헤드가 발생되는 것이다.
데이터가 처리되는 순서에 주목하여 어떤 자료구조를 사용할 지 판단해야 한다.

1. 스택
   • LIFO 순으로 데이터를 처리
   • 중복 제거와 같은 조건에 사용될 수 있음
2. 큐
   • FIFO 순으로 데이터를 처리
   • 처리해야 할 데이터의 크기가 조건에 따라 다를 때 사용할 수 있음