[Python] programmers 3차 압축

1. 문제 링크

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

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

 

2. 문제 요약

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
5. 단계 2로 돌아간다.

3. 아이디어 정리

1. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. ⇒ A~Z까지 딕셔너리에 등록한다.
2. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. ⇒ 투 포인터로 긴 문자열 찾는다.
3. w에 해당하는 사전의 색인 번호를 출력하고, 입력에서 w를 제거한다. ⇒ w에 해당하는 색인을 결과에 추가하고 msg를 업데이트한다.
4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다. ⇒ 남은 글자가 있으면 사전 등록한다.
5. 단계 2로 돌아간다.

 

4. 문제 풀이

4-1. 내풀이

from collections import defaultdict

def solution(msg):
    """
    :return: 주어진 문자열을 압축한 후의 사전 색인 번호를 배열
    """
    def get_long_str():
        """
            가장 긴 문자열 출력
        :return:
        """
        w = msg[0]
        right = 1
        while right < len(msg):
            if dict_[msg[0:right + 1]] != 0:  # 사전에 존재하면, w 변경&더 긴 문자열 있는지 찾기
                w = msg[0:right + 1]
                right += 1
            else:
                break
        return w

    answer = list()
    dict_ = defaultdict(int)
    index = 1
    # 1. 길이가 1인 사전 만들기 (1부터 시작)
    for i in range(ord('A'), ord('Z') + 1):
        dict_[chr(i)] = index
        index += 1
    while msg:
        # 2. 현재 입력과 일치하는 가장 긴 문자열 w 찾기
        w = get_long_str()
        # 3. w 색인 넣기 &  입력에서 w를 제거한다.
        answer.append(dict_[w])
        msg = msg[len(w):]
        # 4. 입력에서 처리되지 않은 다음 글자가 남아있다면(c), w+c에 해당하는 단어를 사전에 등록한다.
        if msg:  # 마지막 글자가 아니면 남은 글자 사전 추가
            dict_[w + msg[0]] = index
            index += 1
        else:
            break
    return answer

 

 

5. 결론

• 구현 문제