[프로그래머스] [3차] 압축(Python)

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/17684?language=python3 

프로그래머스

소스 코드

def solution(msg):
	# {A:1,B:2, ... , Z:26} 딕셔너리 생성
    alphas = {chr(x):x-64 for x in range(65,91)}
    
    results = []
    tmp = '' # 쌓아갈 문자열
    cur = 27 # 딕셔너리 번호
    
    for i in range(len(msg)):
        tmp += msg[i] # 확인하는 글자 추가
        if tmp in alphas: # 딕셔너리에 존재하면 패스
            continue
        else: # 처음보는 문자열이 되면
            alphas[tmp] = cur # 번호와 함께 딕셔너리에 저장
            cur += 1 # 딕셔너리 다음 번호 준비
            # 딕셔너리에서 번호를 뽑아 results에 저장
            results.append(alphas[tmp[:-1]])
            tmp = tmp[-1] # 마지막 글자만 남기기
    
    # 마지막 문자 처리
    if tmp in alphas:
        results.append(alphas[tmp])
    else:
        results.append(cur+1)
        
    return results

 

해설

• 딕셔너리를 이용한 해시 문제 풀이
• 어림잡아 계산한 시간복잡도도 충분한 편
• 후처리

 

해시 + 시간복잡도

문제에서 요구하는 내용을 간단히 정리해보면 다음과 같다.

1. 처음보는 글자가 만들어질 때까지 문자열을 쌓는다.
2. 처음보는 글자가 만들어지면, 마지막에 추가한 문자를 제외한 것들을 딕셔너리의 key로 이용한다.

따라서 문자열 msg를 앞에서부터 탐색하면서 이것이 딕셔너리의 key로 존재하는지 확인해야 한다.

for i in range(len(msg)):
    tmp += msg[i] # 확인하는 글자 추가
    if tmp in alphas: # 딕셔너리에 존재하면 패스
        continue

딕셔너리에서 해당 key값이 존재하는지 확인하는 이 과정의 시간복잡도는 O(1~N)이다. 

최악의 경우 O(N)인 것이고 일반적으로는 리스트에 비해 훨씬 빠르다.

심지어 msg의 길이는 최대 1000글자라고 명시되어 있으므로 시간 초과 판정을 받기 어려운 문제다.

    else:
        alphas[tmp] = cur
        cur += 1
        results.append(alphas[tmp[:-1]])
        tmp = tmp[-1]

처음 보는 문자열이 나타난 경우는 마지막에 추가한 문자열을 제외하고 판단해야 한다.

문제에서 제시해준 예를 생각해보면 KA가 되었을 때 K:11이 호출되고 KA:27이 생성되었다.

 

여기서 K를 제외한 A를 tmp에 들고 있는다.

그리고 AK가 되었을 때 A:1이 호출되고 AK:28이 생성되었다.

 

따라서 새로운 문자열이 생성된 경우 cur를 업데이트 하면서 딕셔너리에 key:value로 저장한다.

그리고 문자열에서는 마지막으로 추가된 문자를 제외한 것들은 다 날려주면 된다.

 

 

후처리

위 과정을 모두 마치면 아직 tmp에 문자열이 남아있을 것이다.

반복문 종료 직전까지 새로운 문자열이 생성되지 않았더라면 continue로 넘겨졌을 것이고,

마지막에 생성이 되었다고 하더라도 tmp = tmp[-1] 에 의해서 한 글자라도 남게 된다.

 

따라서 이를 기존과 동일한 방식으로(딕셔너리에 존재하면 value 불러오기 / 없으면 cur + 1) 처리해야 한다.