[Swift 알고리즘] 프로그래머스(Lv.4) - 가사 검색 / 2020 카카오 블라인드

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

 

오늘은 "프로그래머스(Lv.4) - 가사 검색" 문제를 풀었습니다.

 

---

Github

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

 

문제 링크

코딩테스트 연습 - 가사 검색

 

---

풀이

이번 문제는 Trie 문제입니다. (해시맵으로도 구현 가능)

저번에 Trie 문제를 한 번 풀어본 게 큰 도움이 되었습니다.

 

1. Node 클래스를 생성합니다.

class Node {
    var key: String
    var count: Int = 0 //하위 자식 개수
    var children: [String: Node] = [:]
    
    init(_ key: String) {
        self.key = key
    }
}

key는 노드의 키, count는 경로 개수, children은 하위 노드입니다.

count는 해당 글자를 지나는 단어의 개수입니다.

frodo, frozen, front 라면 f, r의 count는 3이 됩니다. (f, r을 지나는 단어가 3개)

 

2. Trie 클래스를 생성합니다.

Trie에는 root 노드와 insert( ), search( )가 있습니다.

root 노드는 ""로 초기화 됩니다.

 

2-1. insert( ) 구현

항상 root에서 시작하고 한 글자씩 노드를 생성합니다.

노드를 이동하면서 노드의 count를 1씩 증가 시킵니다.

 

2-2. search() 구현

탐색도 root에서 시작합니다.

query를 입력 받아 일치하는 검색어가 몇 개인지 확인합니다.

 

query에서 글자가 나오면 그 글자 노드를 찾아 이동합니다.

query에서 와일드 카드가 나오면 바로 노드의 count를 return 합니다.

 

이것이 가능한 이유는 아래에서 설명합니다.

 

3. 순방향 Trie와 역방향 Trie를 생성합니다.

와일드카드는 접두사와 접미사로 나올 수 있습니다.

접두사는 접미사보다 처리하기 까다롭기 때문에 역방향 Trie를 이용해 접두사도 접미사처럼 처리할 수 있도록 합니다.

 

순방향 Trie에는 word를 한 글자씩 순서대로 insert( )합니다.

역방향 Trie에는 word를 역순으로 한 글자씩 insert( )합니다.

 

query에서 와일드카드가 prefix(접두사)로 있으면 역방향 Trie에서 search 합니다.

와일드카드가 접미사로 있으면 순방향 Trie에서 search 합니다.

 

개수를 return 하면 답입니다.

 

후기

저번 문제에서 배운 Trie를 응용하여 푼 문제였습니다.

자료 구조 하나 배운 덕에 또 한 문제를 풀었네요.

물론... 전부 저의 힘으로 풀진 못했고 아쉽게도 도움을 받았습니다.

그래도 어떤 자료구조를 사용하면 될지 안다는 것부터 참으로 뿌듯한 일입니다.

 

감사합니다!

 

---

전체 코드

import Foundation

class Node {
    var key: String
    var count: Int = 0 //하위 자식 개수
    var children: [String: Node] = [:]
    
    init(_ key: String) {
        self.key = key
    }
}

class Trie {
    var root: Node
    
    init() {
        self.root = Node("")
    }
    
    func insert(_ word: String) {
        var currentNode = self.root
        
        for char in word {
            let str: String = String(char)
            currentNode.count += 1
            if currentNode.children[str] == nil {
                currentNode.children[str] = Node(str)
            }
            
            currentNode = currentNode.children[str]!
        }
    }
    
    func search(_ query: String) -> Int {
        var currentNode = self.root        
        for char in query {
            let str = String(char)
            if str == "?" {
                return currentNode.count
            }
            
            if currentNode.children[str] == nil {
                return 0 //마지막 글자
            }
            
            currentNode = currentNode.children[str]!
        }
        
        return currentNode.count
    }
}

func solution(_ words:[String], _ queries:[String]) -> [Int] {
    var result: [Int] = []
    
    var tries: [Int: Trie] = [:]
    var reversedTries: [Int: Trie] = [:]
    
    for word in words {
       if tries[word.count] == nil {
           tries[word.count] = Trie()
           reversedTries[word.count] = Trie()
       }
        
       tries[word.count]?.insert(word)
       reversedTries[word.count]?.insert(String(word.reversed()))
    }
    
    for query in queries {
        var count = 0
        if query.hasPrefix("?") { //와일드카드가 접두사로
            if let reversedTrie = reversedTries[query.count] {
                let reversedQuery = String(query.reversed())
                count = reversedTrie.search(reversedQuery)
            }
        } else { //접미사로
            if let trie = tries[query.count] {
                count = trie.search(query)
            }
        }
        result.append(count)
    }
    
    // print("result: \(result)")
    return result
}

---

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

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

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