[Python] 압축 - 문자열

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

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

생각과정

- 딕셔너리를 만들어 새로운 문자 패턴을 저장한다.

- 주어진 문자열을 순회하면서 현재 입력된 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다.

- 현재 입력된 문자의 다음 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다. 이때 현재 입력 문자에 다음 문자를 더한 패턴도 딕셔너리에 추가하고 다음 반복으로 바로 넘어간다. ex) 현재:A 다음:B일때, B가 딕셔너리에 없으면 B와 AB를 추가한다.

- 다음 문자가 딕셔너리에 있다면 사전에 등록되어 있는 가장 긴 문자열을 찾아 출력한다. 현재 문자의 인덱스부터 출발해 주어진 문자열의 끝까지 순회하면서 해당 패턴이 딕셔너리에 없으면 이전 패턴을 출력한다.

- 딕셔너리에서 패턴을 찾아 출력했다면, 패턴의 길이만큼 검사를 생략한다.

 

구현

def solution(msg):
    answer = []
    dic = {}
    max_dict = 26
    loop_till = -1
    for i in range(len(msg)):
        if loop_till > i:
            continue
        # 사전 검사 - 현재 입력
        if msg[i] not in dic.keys():
            dic[msg[i]] = ord(msg[i]) - 64
            if i == len(msg)-1:
                answer.append(dic[msg[i]])
                break

        # 사전 검사 - 다음 입력
        if i+1 < len(msg):
            if msg[i+1] not in dic.keys():
                dic[msg[i+1]] = ord(msg[i+1]) - 64
                max_dict += 1
                dic[msg[i:i+2]] = max_dict
                
                answer.append(dic[msg[i]])
                print('append ', msg[i])
                continue
                
        # 사전에 등록되어있는 가장 긴 문자열 찾기
        max_length = msg[i: i+1]
        found = False
        for j in range(i+1, len(msg)):
            if msg[i:j+1] not in dic.keys():
                max_dict += 1
                dic[msg[i:j+1]] = max_dict
                dic[msg[j]] = ord(msg[j])-64
                found = True
                break
            max_length = msg[i:j+1]
        
        if found == False and len(max_length) != 2:
            if i+len(max_length) == len(msg):
                loop_till = i+len(max_length)
            answer.append(dic[max_length])
        else:
            loop_till = i+ len(max_length)
            if i+len(max_length) >= len(msg) and len(max_length) == 2:
                if max_length[0] == max_length[1]:
                    max_length = max_length[:-1]
                    loop_till = i+ 2
            answer.append(dic[max_length])
    return answer

결과

 

 

문자를 아스키코드로 변환하는 함수 

ord(string)

 

아스키코드를 문자로 변환하는 함수

chr(ascii)

 

참고

https://lsjsj92.tistory.com/201

파이썬 문자를 아스키로, 아스키 코드를 문자로