[프로그래머스] 압축

문제 요약

영문 대문자로 이루어진 문자열을 LZW 압축 알고리즘으로 압축한다.

LZW 압축은 다음 과정을 반복한다.

1. 길이가 1인 모든 단어로 사전 초기화
2. 현재 입력과 일치하는 가장 긴 문자열 w 탐색
3. w의 사전 색인 번호 출력
4. 처리할 다음 글자 c가 있다면 w + c를 사전에 추가
5. 남은 입력에 대해 반복

출력된 사전 색인 번호들을 배열에 담아 반환해야 한다.

핵심 아이디어

사전에 등록된 문자열과 색인 번호를 딕셔너리로 관리한다.

현재까지 찾은 가장 긴 문자열을 current에 저장하고, 다음 글자를 붙인 candidate가 사전에 있는지 확인한다.

candidate = current + character

candidate가 사전에 있다면 더 긴 문자열을 찾은 것이므로 current를 갱신한다.

current = candidate

candidate가 사전에 없다면 현재 current가 사전에 존재하는 가장 긴 문자열이다.

이때 current의 색인 번호를 출력하고 candidate를 새 사전 항목으로 등록한다.

answer.append(dictionary[current])
dictionary[candidate] = next_index

그 뒤 현재 글자부터 다시 가장 긴 문자열을 찾기 시작한다.

current = character

사전 초기화

문제에서 처음 사전에는 A부터 Z까지 한 글자 단어가 순서대로 들어 있다.

1: A
2: B
...
26: Z

파이썬에서는 알파벳 순서와 색인 번호를 이용해 다음과 같이 만들 수 있다.

dictionary = {
    chr(code): code - ord("A") + 1
    for code in range(ord("A"), ord("Z") + 1)
}

chr은 문자 코드 값을 문자로 바꾸는 함수다.

chr(65)  # "A"
chr(90)  # "Z"

새로운 사전 항목의 번호는 27부터 시작한다.

next_index = 27

가장 긴 문자열 찾기

문자열을 왼쪽부터 한 글자씩 확인한다.

current = ""

for character in msg:
    candidate = current + character

candidate가 이미 사전에 등록되어 있으면 current를 계속 확장할 수 있다.

if candidate in dictionary:
    current = candidate

candidate가 사전에 없다면, candidate에서 마지막 글자를 제외한 current가 현재 입력과 일치하는 가장 긴 문자열이다.

else:
    answer.append(dictionary[current])
    dictionary[candidate] = next_index
    next_index += 1
    current = character

반복문이 끝난 뒤에는 마지막 current가 아직 출력되지 않은 상태다.

따라서 마지막 색인 번호를 추가해야 한다.

answer.append(dictionary[current])

풀이 과정

1. 사전 초기화

dictionary = {
    chr(code): code - ord("A") + 1
    for code in range(ord("A"), ord("Z") + 1)
}
next_index = 27

2. 결과 배열과 현재 문자열 초기화

answer = []
current = ""

3. 각 글자를 붙인 후보 문자열 확인

for character in msg:
    candidate = current + character

4. 후보가 사전에 있는 경우

if candidate in dictionary:
    current = candidate

더 긴 사전 단어를 찾았으므로 다음 글자를 계속 확인한다.

5. 후보가 사전에 없는 경우

else:
    answer.append(dictionary[current])
    dictionary[candidate] = next_index
    next_index += 1
    current = character

가장 긴 문자열의 색인 번호를 출력하고, 현재 문자열과 다음 글자를 합친 후보를 사전에 추가한다.

6. 마지막 문자열 출력

answer.append(dictionary[current])

반복문 안에서는 새 단어를 등록할 때만 색인 번호를 출력한다.

마지막 단어는 다음 글자가 없어 사전에 새 단어를 추가하지 않으므로 반복문 밖에서 따로 출력한다.

Python 코드

def solution(msg):
    # A부터 Z까지 사전을 초기화한다.
    dictionary = {
        chr(code): code - ord("A") + 1
        for code in range(ord("A"), ord("Z") + 1)
    }

    next_index = 27
    answer = []
    current = ""

    for character in msg:
        candidate = current + character

        # 후보 문자열이 사전에 있으면 더 긴 문자열을 찾는다.
        if candidate in dictionary:
            current = candidate
            continue

        # current가 현재 입력과 일치하는 가장 긴 문자열이다.
        answer.append(dictionary[current])

        # current와 다음 글자를 합친 문자열을 사전에 추가한다.
        dictionary[candidate] = next_index
        next_index += 1

        # 현재 글자부터 다시 탐색을 시작한다.
        current = character

    # 마지막 문자열의 색인 번호를 출력한다.
    answer.append(dictionary[current])

    return answer

코드 설명

dictionary

dictionary = {
    chr(code): code - ord("A") + 1
    for code in range(ord("A"), ord("Z") + 1)
}

문자열을 키로, 사전 색인 번호를 값으로 저장한다.

딕셔너리를 사용하면 문자열이 사전에 존재하는지 빠르게 확인할 수 있다.

current

current = ""

현재 입력에서 사전에 존재하는 가장 긴 문자열을 저장한다.

candidate가 사전에 존재할 때만 current를 갱신하므로, candidate가 없어진 순간 current는 항상 가장 긴 일치 문자열이다.

candidate

candidate = current + character

현재 가장 긴 문자열에 다음 글자를 하나 붙인 후보 문자열이다.

후보가 사전에 없다면 LZW 규칙에 따라 다음 두 작업을 수행한다.

current의 색인 번호 출력
candidate를 새 사전 항목으로 추가

next_index

next_index = 27

초기 사전의 색인 번호는 1부터 26까지 사용한다.

새로운 문자열을 추가할 때마다 next_index를 사용한 뒤 1 증가시킨다.

마지막 출력

answer.append(dictionary[current])

마지막 문자열은 다음 글자가 없어서 candidate가 사전에 없어진 경우가 발생하지 않을 수 있다.

따라서 반복문이 끝난 뒤 남아 있는 current의 색인 번호를 반드시 추가해야 한다.

예시 1

입력이 다음과 같다고 하자.

msg = "KAKAO"

압축 과정은 다음과 같다.

현재 문자열 w	다음 글자 c	출력	사전 추가
K	A	11	27: KA
A	K	1	28: AK
KA	O	27	29: KAO
O	없음	15	없음

따라서 결과는 다음과 같다.

[11, 1, 27, 15]

예시 2

입력이 다음과 같다고 하자.

msg = "TOBEORNOTTOBEORTOBEORNOT"

LZW 규칙을 적용하면 결과는 다음과 같다.

[20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34]

시간 복잡도

입력 문자열의 길이를 N이라고 하자.

문자열을 한 번 순회하며 각 단계에서 딕셔너리 조회와 삽입을 수행한다.

O(N)

문자열 연결과 해시 계산 비용은 문자열 길이에 영향을 받을 수 있지만, 이 문제의 입력 길이는 최대 1000이므로 충분히 처리할 수 있다.

공간 복잡도

초기 사전과 새로 추가되는 문자열을 저장한다.

최악의 경우 입력 길이에 비례하는 수의 사전 항목이 추가된다.

O(N)

정리

이 문제는 LZW 압축 알고리즘의 사전 생성 규칙을 구현하는 문제다.

사전에 A부터 Z까지 등록
현재 가장 긴 일치 문자열 current 유지
다음 글자를 붙인 candidate 확인
candidate가 없으면 current의 색인 번호 출력
candidate를 새 사전 항목으로 등록
마지막 current의 색인 번호 추가

현재 문자열을 확장하다가 사전에 없는 후보를 만났을 때 출력과 사전 추가를 함께 수행하는 것이 핵심이다.