프로그래머스 - 압축

https://school.programmers.co.kr/learn/courses/30/lessons/17684

프로그래머스

 

탐색 문제

 

입력도 1000글자 이하라서 시간 복잡도도 크게 신경쓰지 않아도 될 듯하다.

 

메시지 압축을 위해 딕셔너리를 만들어 두고 글자를 순회하며 없는 글자면 추가하고 있는 글자면 없을 때까지 순회하면 된다.

 

메시지 순회는 while문으로 했다. 이유는 이미 있는 단어라면 해당 단어에 포함된 index를 건너뛰어야하는 상황이 오기 때문이다.

 

두번째 순회도 while로 했다. 탈출문도 확실하고 조건 검사도 계속해야하니까

 

1. 순회 전에 앞서 이미 압축처리 할 수 있게 매핑된 A~Z는 미리 딕셔너리에 저장해두어야 한다.

1-1. 해당 딕셔너리의 마지막 key는 26이고 새로 압축될 단어는 27부터 저장되기 때문에

        last_dict_index를 27로 선언해둔다.

 

2. while문을 순회하며 word는 해당 인덱스의 글자로 선언한다.

2-1. answer의 마지막을 계속해서 변경해줄 것이기 때문에 미리 추가해둔다.

 

3. 두번째 while문을 들어가며 word가 사전 압축된 단어인지 검사한다.

3-1. 사전에 압축된 단어이니 answer의 마지막을 update해준다.

3-2. 그 다음 다음 인덱스를 탐색

3-3. 다음 인덱스가 유효 범위 이내라면 word에 글자를 추가한다.

3-4. 유효 범위 밖이라면 탐색이 끝까지 끝난 것이다. 때문에 index를 일부러 msg보다 크게하여 모든 while문을 종료시킬 것이다.

 

4. while문이 break가 아닌 정상 종료될시 시작되는 else구문

사전 압축 딕셔너리의 get에서 False된 것이기 때문에 단어를 등록해줌

4-1. 그러면서 index를 update 해준다.

 

 

def solution(msg):
    answer = []

    dictionary = {}

    for i in range(1,27):
        dictionary[chr(i+64)] = i

    last_dict_index = 27
    index = 0
    max_length_minus_one = len(msg) - 1

    while index < len(msg):
        word = msg[index]
        answer += [1]
        while_2nd_index = index
        while dictionary.get(word):
            answer[-1] = dictionary[word]
            while_2nd_index += 1
            if while_2nd_index < len(msg):
                word += msg[while_2nd_index]
            else:
                index = len(msg) + 1
                break
        else:
            if not dictionary.get(word):
                dictionary[word] = last_dict_index
                last_dict_index += 1
                index = while_2nd_index - 1
        index += 1

    return answer