Level 2. 압축

압축

코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > 압축

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

문제 설명

여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW(Lempel–Ziv–Welch) 압축을 구현

- 입력: 대문자로만 이루어진 문자열
- 과정:
  1. 길이가 1인 모든 단어를 포함하는 리스트 생성
  2. 현재 입력과 일치하는 가장 긴 문자열 w 를 찾아 위치값을 반환하고 입력에서 w를 제거
  3. 입력에서 처리되지 않은 글자가 남아있다면(c) 새로운 단어(w+c)를 리스트에 등록
  4. 단계 반복

문제 풀이

#00
msg = 'KAKAO'
#01 문자열 dic 생성
dic = {chr(65+i):i+1 for i in range(26)}
#02
answer = []
p1,p2 = 0,0 #고려할 원소 초기 설정
while True:
    p2+=1
    if p2 == len(msg): #문자열 끝까지 도달했을 때,
        answer.append(dic[msg[p1:p2]]) # dic의 msg[p1,p2]값을 answer에 삽입
        break
    if msg[p1:p2+1] not in dic: # msg[p1,p2+1]이 dic에 존재하지 않을 때,
        dic[msg[p1:p2+1]] = len(dic)+1 # dic에 msg[p1,p2+1]:len(dic)+1 추가
        answer.append(dic[msg[p1:p2]]) # dic의 msg[p1,p2]값을 answer에 삽입
        p1 = p2 #시작 위치를 p2로 변경
#03
answer

전체 코드

def solution(msg):
    answer = []

    dic = {chr(65+i):i+1 for i in range(26)}
    p1,p2 = 0,0
    while True:
        p2+=1
        if p2 == len(msg):
            answer.append(dic[msg[p1:p2]])
            break
        if msg[p1:p2+1] not in dic:
            dic[msg[p1:p2+1]] = len(dic)+1
            answer.append(dic[msg[p1:p2]])
            p1 = p2
    return answer

# Code test
msg = 'TOBEORNOTTOBEORTOBEORNOT'
solution(msg)

while문을 반복하며 시작점과 끝점을 갱신하며 푸는 것이 포인트