[ Lv 2 ] [3차] 압축

풀이 과정

---

1. 현재 문자 기준으로 오른쪽으로 문자 한개씩 늘려가며 슬라이싱 후 딕셔너리에서 찾아 봄.

2. 가장 길게 매칭되어야 하므로 딕셔너리에서 찾지 못할때까지 한개씩 늘려감.

3. 찾지 못한다면 [현재 시점 ~ 찾지 못한 시점] 까지의 문자열을 딕셔너리에 넣어준 후, 찾지 못한 시점으로 점프해주면 된다. 단, 여기서 찾지 못한 시점을 찾을수 없는 경우(현재~끝까지 매칭됨) 딕셔너리에 넣어준 후 종료한다.

4. 위 과정을 전체 문자열에 적용한다.

---

def solution(msg):
    words = {chr(i):idx+1 for idx, i in enumerate(range(ord('A'), ord('Z')+1))}
    posfrom = 0
    nextidx = 27
    answer = []
    nextpos = 0

    while True:
        check = False
        for i in range(posfrom+1, len(msg)+1):
            if words.get(msg[posfrom:i]) == None:
                check = True
                words[msg[posfrom:i]] = nextidx
                nextpos = i-1
                nextidx += 1
                break

        if check:
            answer.append(words[msg[posfrom:nextpos]])
        else:
            answer.append(words[msg[posfrom:]])
            break

        posfrom = nextpos          

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges