[프로그래머스] 3차 압축 swift

문제 설명

LZW 압축 단계는 위와 같다.

사실.. 이 부분만 보곤 문제 이해를 못했다.

 

입출력 예제를 보고 문제를 겨우 이해했다...

간단히 말하면 현재 사전에 있는 단어의 최대 길이를 찾고 그 색인 번호를 저장한다.

그리고 위에 찾은 단어+다음 단어를 사전에 등록한다.

 

예를 들어 ABAB가 있을 때

1. A 의 색인번호 1을 출력한다. 그 다음 단어인 B를 포함한 AB를 27로 사전에 넣는다.

2. B의 색인번호 2을 출력한다. 그 다음 단어인 A를 포함한 BA를 28로 사전에 넣는다.

3. AB의 색인번호 27을 출력한다. 다음 단어는 없으니 사전에 넣을 게 없다.

 

 

문제 풀이

이 문제의 핵심은 사전에 있는 단어의 길이를 최대로 찾는 것

예를 들어 ~ABCDEF가 있을 때 사전에 AB도 있고 ABC도 있다고 가정해본다.

for문을 돌며 msg의 문자 하나하나씩 체크해본다.

 

1. 현재 문자는 A: 먼저 A를 체크한다. 사전에 있다. -> A를 저장하고 다음 문자로 넘어간다.

2. 현재 문자는 B: 아까 저장해둔 A에 B를 더한 AB를 체크한다. 사전에 있다. -> AB를 저장하고 다음 문자로 넘어간다.

3. 현재 문자는 C: 아까 저장해둔 AB에 C를 더한 ABC를 체크한다. 사전에 있다. -> ABC를 저장하고 다음 문자로 넘어간다.

4. 현재 문자는 D: 아까 저장해둔 ABC에 D를 더한 ABCD를 체크한다. 사전에 없다. -> ABC의 색인번호를 답에 넣는다. ABCD를 사전에 추가한다.

 

 

이런 식의 풀이법으로 문제를 풀어보았다.

 

 

코드

func solution(_ msg:String) -> [Int] {
    let msg = msg.map { String($0) }
    var dictionary = [String: Int]()
    var answer = [Int]()
    var num = 26
    
    // A~Z 딕셔너리에 넣어줌
    for i in 1...num {
        let alphabet = String(UnicodeScalar(64+i)!)
        dictionary[alphabet] = i
    }
    
    var w: String = "" // 현재 문자열
    var wc: String = "" // 현재 문자열+다음 문자열
    for i in 0..<msg.count {
        w += msg[i]
        
        if i == msg.count-1 { // 마지막 문자열이면 현재 문자열 색인번호 넣고 끝냄
            answer.append(dictionary[w]!)
            break
        } else {
            wc = w+msg[i+1] // 다음문자열을 더한 wc
        }
        
        if dictionary[wc] == nil { // wc가 사전에 없다면
            num += 1
            dictionary[wc] = num // wc를 사전에 넣어줌
            answer.append(dictionary[w]!) // 답엔 w를 넣어줌
            w = "" // w와 wc 빈 값으로 초기화
            wc = ""
        }
    }
    return answer
}

 

후기

헤맸던 부분은 색인번호를 넣을때 딕셔너리의 last의 색인번호 +1 하는 식으로 구현하려했는데.. 딕셔너리가 넣은 순서대로 정렬되지 않는다는 사실을 잊어버렸따..ㅋㅋ

그래서 num라는 변수를 따로 만들어 넣을 때마다 num+=1 해주었다.

 

처음에 문제 이해하는데 조금 걸렸지만.. 문제만 이해하고 나면 단순 구현 문제이다.