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

문제 링크

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

코딩테스트 연습 - [3차] 압축

 

풀이 

- 딕셔너리 사용한 구현 문제 

- 사전은 단어를 key, 색인 번호를 value로 가진다. 

1. A부터 Z까지 사전에 등록 

- A의 아스키 코드값 65 

 

2. 단어의 시작 위치부터 뒷 알파벳들 하나씩 붙인 단어에 대하여

사전에 존재한다면, 색인 번호 갱신

존재하지 않는다면, 그 전 Index까지는 존재하는 단어였다는 뜻이므로 새로운 단어 시작 위치 index 에 갱신하고 break 

 

만약 마지막 알파벳까지 비교했는데 사전에 존재하는 단어라면, 중단해주기 위해서 index를 len(msg)로 설정 

또한, 비교 전 index가 len(msg)-1 이라면 마지막 한 알파벳이라는 뜻이므로 색인 번호 추가해주고, break 

 

3. 새로운 단어 사전에 색인 번호 등록하고, 압축할 색인 번호 answer에 추가 

 

def solution(msg):
    answer = []
    # 체크할 단어 위치 
    index = 0 
    # 단어 key, value는 색인 번호 
    dic = {} 
    # 다음 색인 번호 
    cnt = 27
    
    # A부터 Z까지 사전에 등록 
    for i in range(65, 99):
        dic[chr(i)] = i - 64
    

    while index < len(msg) :
		# 압축할 색인 번호 
        num = dic[msg[index]]
        s = ''
        # 현재 알파벳의 인덱스 위치 
        t = index 
        
        # 마지막 한개 알파벳이라면 
        if index == len(msg) -1 :
            answer.append(num)
            break
        
        for i in range(t+1, len(msg)+1):
			
            # 사전에 없는 단어라면 
            if msg[t:i] not in dic :
                s = msg[t:i]
                # 그 전까지 단어는 사전에 있었다는 뜻이므로 제거 후, 다음 알파벳부터 비교 
                index = i -1
                break
            # 사전에 있는 최대 길이의 단어까지 색인 번호 갱신 
            else:
                num = dic[msg[t:i]]
            
            # 단어 끝까지 존재하는 색인번호가 존재한다면 중단 
            if i == len(msg):
                index = len(msg)
        
        # 색인 번호 등록 
        dic[s] = cnt 
        # 다음 등록할 색인 번호 + 1
        cnt += 1 
        # 압축할 색인 번호 추가 
        answer.append(num)

    return answer