[프로그래머스][카카오] 압축

문제

주어진 string을 LZW 압축한 후 색인 번호를 출력하시오.

문제 출처: 프로그래머스(https://programmers.co.kr/learn/courses/30/lessons/17684)

풀이

어렵게 보였지만 꽤 간단하게 풀린 문제였습니다.(근데 이 문제의 정답률이 무려 95.80%.. 3차까지 가신 분들은 대단해..) LZW 압축 알고리즘을 구현하는 문제인데 저는 처음 들어보는 알고리즘이었지만 설명이 친절하게 적혀있어서 하나씩 따라서 풀어가면 됩니다. 사전을 이용하라는 말에 바로 map을 이용해야겠다고 생각했습니다. 주어진 문자열 msg의 에서 제일 첫 문자에서 시작합니다. 첫 문자는 한글자이기 때문에 당연히 색인에 존재할 것입니다. 이후부터는 색인에 속하는 가장 긴 문자열 w를 찾는 부분과 w를 찾으려 할 때 msg의 가장 마지막 자리일 경우에만 잘 처리해주면 됩니다. 가장 긴 문자열 w를 찾기 위해서는 글자를 붙여가며 사전에 있는지 찾아보다가 사전에 존재하지 않는다면 그 전의 문자열이 가장 긴 w이기 때문에 해당 문자열의 색인번호를 answer에 추가해주고 해당하는 새로운 문자열은 색인에 추가해주도록 했습니다. 가장 긴 문자열을 찾으려할 때 만약 msg의 가장 마지막 문자열을 붙였다면 그 문자열까지가 가장 긴 문자열 w에 해당하므로 색인 번호를 추가해주도록 했습니다.

(해설: http://tech.kakao.com/2017/11/14/kakao-blind-recruitment-round-3/)

코드

https://github.com/kswim/Algorithm/blob/master/etc/17684.cpp