문제:
풀이방법:
LZW 압축 과정대로 코드를 작성하면 된다.
우선 길이가 1인 모든 단어를 포함해서 사전을 구축해야 하므로 dictionary에 밑과 같이 구축한다. 그 뒤에 idx가 입력으로 들어온 문자열의 길이와 같아질 때까지 반복해서 확인하고 추가하는 작업을 한다.
LZW 압축과정은 다음과 같이 작동된다.
1. KAKAO의 경우에 KAKAO와 인덱스 0 그리고 사전이 check로 입력된다.
2. 이를 뒤에서부터 비교를 한다. 즉 KAKAO가 사전에 있는가? -> KAKA가 사전에 있는가? -> .... 순으로 진행이 되고 K가 사전에 있는가에서 참이므로 break를 걸고 반복문 밖으로 나온다.
3. 그러면 KA는 사전에 없는 단어였으므로 사전에 추가하고 인덱스와 사전을 반환한다.
4. check에서 나온 인덱스와 check에 넣기 전에 사용한 인덱스를 사용해서 슬라이싱을 하고 이를 사전의 색인 번호를 answer에 추가한다.
5. idx를 i로 지정한다.
idx가 msg와 동일할 떄까지 진행을 하면 압축과정이 끝나게 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
def check(msg,idx,dictionary):
for i in range(len(msg),idx,-1):
if msg[idx:i] in dictionary:
break
dictionary.append(msg[idx:i+1])
return i,dictionary
def solution(msg):
dictionary=[' ','A','B','C','D','E','F','G','H','I','J',
'K','L','M','N','O','P','Q','R','S','T','U',
'V','W','X','Y','Z']
answer=[]
idx=0
while len(msg)!=idx:
i,dictionary=check(msg,idx,dictionary)
answer.append(dictionary.index(msg[idx:i]))
idx=i
return answer
|
cs |
문제링크:
https://programmers.co.kr/learn/courses/30/lessons/17684
코딩테스트 연습 - [3차] 압축 | 프로그래머스
TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]
programmers.co.kr
'Algorithm > Python' 카테고리의 다른 글
| [Programmers]2018 Kakao. n진수 게임 (0) | 2019.12.04 |
|---|---|
| [Programmers]2018 Kakao.파일명 정렬 (0) | 2019.12.03 |
| [Programmers]2018 Kakao.방금그곡 (0) | 2019.12.01 |
| [Programmers]2020 Kakao.괄호 변환 (0) | 2019.11.15 |
| [Programmers]2020 Kakao. 문자열 압축 (0) | 2019.11.14 |