[Swift] 프로그래머스 - 압축

문제

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

LZW압축..

과정은 방법과 예시를 보면 이해가 된다. 단 3번에서 입력에서 w제거 부분이 이해가 잘 안된다 =_=.. 이부분을 제거해줬던걸 빼줬더니 통과했다.

과정

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

예제

예를 들어 입력으로 KAKAO가 들어온다고 하자.

1. 현재 사전에는 KAKAO의 첫 글자 K는 등록되어 있으나, 두 번째 글자까지인 KA는 없으므로, 첫 글자 K에 해당하는 색인 번호 11을 출력하고, 다음 글자인 A를 포함한 KA를 사전에 27 번째로 등록한다.
2. 두 번째 글자 A는 사전에 있으나, 세 번째 글자까지인 AK는 사전에 없으므로, A의 색인 번호 1을 출력하고, AK를 사전에 28 번째로 등록한다.
3. 세 번째 글자에서 시작하는 KA가 사전에 있으므로, KA에 해당하는 색인 번호 27을 출력하고, 다음 글자 O를 포함한 KAO를 29 번째로 등록한다.
4. 마지막으로 처리되지 않은 글자 O에 해당하는 색인 번호 15를 출력한다.

이 과정을 거쳐 다섯 글자의 문장 KAKAO가 4개의 색인 번호 [11, 1, 27, 15]로 압축된다.

인풋값

압축할 문자열 msg

return값

압축한 idx값 array

주의할 점

• 문제를 잘 읽자

접근 방법

과정대로 돌리면 된다.

처음엔 array를 사용해서 기록하는식으로 구현했다가, 값에 바로 접근할 수 있는 딕셔너리로 바꿧다.

가장 긴 문장을 서치하는 부분도, 시작점부터 msg 끝까지 서치할 필요가 없고, 지금까지 넣었던 데이터 중 가장 긴 길이만큼만 서치를 하면 된다.

문제 설명 중 사용한 w는 삭제한다고 적혀있는데, 테스트케이스4번에서 실패해서 디버깅 해보니 삭제가 안되야 답으로 인정이 되길래 이부분을 지웠더니 테스트케이스 4번이 통과했다.

코드

왜 안되지 하면서 고민했던 문제인데, 질문도 4개밖에 없어서.. 문제이해를 잘못한 것때문에 실패가 떳다는것에 허무함을 느낀 문제였다 =_=..