[Swift 알고리즘] 프로그래머스(Lv.4) - [3차] 자동완성 / 2018 카카오 블라인드

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.4) - [3차] 자동완성" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - [3차] 자동완성

 

---

풀이

이번 문제는 트라이(Trie) 문제였습니다.

저는 트라이 자료구조라는 것을 이 문제를 풀면서 알게 되었습니다.

 

트라이란 트리에서 확장된 자료구조로 문자열의 관리를 위한 트리입니다.

트라이에 대한 자세한 것은 제가 참고한 아래 링크를 참고해 주세요. 제 블로그에도... 정리를 할지는 잘 모르겠네요.

[ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++)

 

1. 트라이의 Node 클래스 구현하기

트라이에서 사용할 Node 클래스를 구현하였습니다.

class Node {
    var key: Character?
    var data: String?
    var children: [Character: Node] = [:]
    var order: Int = 0
    
    init (_ key: Character?, data: String? = nil) {
        self.key = key
        self.data = data
    }
}

key는 노드의 이름입니다. g 노드, o 노드 이런 식으로 사용할 예정이에요.

data는 마지막 원소인지 아닌지 확인하는 용도입니다. nil 이라면 한 단어의 중간 글자이고 값이 들어있다면 한 단어의 끝 글자입니다.

children은 트리의 자식 노드를 나타낸 디렉토리입니다.

order는 등장한 횟수 입니다.

 

2. 트라이 구현하기

2-1. head 입니다.

var head: Node

트리의 root를 나타내는 노드입니다.

 

2-2. 노드 추가 함수 insert를 구현합니다.

시작은 항상 head에서 합니다. 

word의 첫 글자는 항상 head의 자식 노드가 됩니다.

 

word의 글자를 하나씩 살펴보면서 노드가 있는지 확인합니다.

노드가 없다면 key: 현재 글자, data: nil, order: 0 인 노드를 생성합니다.

생성 후 order를 1 증가 시키고 커서를 생성한 노드로 움직입니다.

 

노드가 있다면 order만 1 증가 시키고 노드를 움직입니다.

 

만약 마지막 글자라면 노드의 data는 word로 설정합니다.

이는 마지막 글자라는 것을 find에서 알 수 있도록 하는 작업입니다.

 

첫 번째 예시인 go -> gone -> guild 으로 insert를 완료하면 아래 그림처럼 됩니다.

 

위 그림을 보면 order가 무엇을 의미하는지 이해가 확 되실 거 같습니다.

총 단어가 3개이기 때문에 head의 order는 3입니다.

g로 시작한 단어가 3개이기 때문에 g의 order도 3입니다.

 

o와 e, d는 각각 go, gone, guild의 마지막 글자이기 때문에 data가 word 그 자체입니다.

 

이렇게 까지 하고 find로 넘어갑시다.

 

2-3. count 계산 함수 find 구현하기

find도 시작은 항상 head에서 시작합니다.

count = 0으로 초기화합니다.

 

word의 글자 하나씩 탐색합니다.

글자 하나마다 count를 1씩 증가 시킵니다.

 

만약 노드의 data가 word와 동일하다면 count를 return 합니다.

이는 마지막 글자까지 모두 입력한 경우입니다.

 

노드의 order가 1이고 data가 nil인 경우에도 count를 return 합니다.

이는 자동 완성이 되는 유니크한 단어까지 입력을 했다는 의미입니다.

따라서 이 경우에도 현재 입력한 개수인 count를 return 하면 됩니다.

 

3. count의 합을 return 합니다.

모든 word에 대한 count의 합을 구합니다.

이 합이 답입니다.

 

후기

너무너무 어려웠던 문제였습니다.

일단 트라이라는 자료 구조를 처음 알게 되어 반가우면서 내가 이 문제를 시험에서 봤다면

어떻게 됐을까하는 걱정도 많이 들었습니다.

속상하면서 더 열심히 해야지라는 각오를 다지게 된 문제였습니다.

 

감사합니다!

---

전체 코드

import Foundation 

class Node {
    var key: Character?
    var data: String?
    var children: [Character: Node] = [:]
    var order: Int = 0
    
    init (_ key: Character?, data: String? = nil) {
        self.key = key
        self.data = data
    }
}

class Trie {
    var head: Node
    
    init() {
        self.head = Node(nil)
    }
    
    func insert(_ str: String) {
        var currentNode = self.head
        
        for ch in str {
            if currentNode.children[ch] == nil {
                currentNode.children[ch] = Node(ch)
            }
            
            currentNode.order += 1
            currentNode = currentNode.children[ch]!
        }
        
        currentNode.data = str
    }
    
    func countFindWord(_ word: String) -> Int {
        var currentNode = self.head
        var count = 0
        
        for ch in word {
            currentNode = currentNode.children[ch]!
            count += 1
            
            if currentNode.data == word || 
                (currentNode.order == 1 && currentNode.data == nil) {
                return count
            }
        }
        
        return count
    }
}

func solution(_ words:[String]) -> Int {
    let trie = Trie()
    for word in words {
        trie.insert(word)
    }
    
    var result = 0
    for word in words {
        result += trie.countFindWord(word)
    }
    
    return result
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.