프로그래머스 - [3차] 압축

문제

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

프로그래머스

 

 

풀이

길이가 가장 긴 문자열을 찾기 위해 인덱스 두 개를 사용한다.

문자열의 시작 인덱스 start_idx와 문자열의 끝 인덱스 end_idx를 이용하고, end_idx의 값을 증가하면서 가장 긴 문자열을 찾는다.

msg[start_idx : end_idx]에 해당하는 문자열이 사전에서 못 찾을때까지 end_idx를 증가시키면 가장 긴 문자열을 찾을 수 있다.

그러면 사전에서 못 찾은 문자열이 나왔을 때 end_idx - 1 까지가 사전에서 찾을 수 있는 가장 긴 문자열이다.

이를 answer 리스트에 추가한다.

그리고 사전에서 못 찾은 문자열 msg[start_idx : end_idx]을 그대로 사전에 추가한다.

 

start_idx 부터 end_idx 까지의 문자열을 찾았으므로 다음은 end_idx 부터 찾아야한다.

그러므로 start_idx = end_idx를 해준다.

 

 

코드

python

def solution(msg):
    answer = []
    
    word_dic = {}
    for alphabet in range(ord('A'), ord('Z') + 1):
        word_dic[chr(alphabet)] = len(word_dic) + 1
    
    start_idx, end_idx = 0, 0
    while end_idx != len(msg):
        if msg[start_idx : end_idx + 1] not in word_dic:
            answer.append(word_dic[msg[start_idx : end_idx]])
            word_dic[msg[start_idx : end_idx + 1]] = len(word_dic) + 1
            start_idx = end_idx
        
        end_idx += 1
        
    answer.append(word_dic[msg[start_idx : end_idx]])
 
    return answer