백준 - 문자열 집합 (14425)

Trie를 이용한 풀이 (시간 초과)

class TrieNode {
    var children: [Character: TrieNode] = [:]
    var isEnd = false
}

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])
var root = TrieNode()

// 트라이 구축
for _ in 0..<N {
    let str = readLine()!
    var now = root
    for (index, letter) in str.enumerated() {
        if let next = now.children[letter] {
            now = next
        } else {
            now.children[letter] = TrieNode()
            now = now.children[letter]!
        }
        if index == str.count - 1 {
            now.isEnd = true
        }
    }
}

// M개의 문자열 탐색
var answer = 0

for _ in 0..<M {
    let str = readLine()!
    var now = root
    for (index, letter) in str.enumerated() {
        if let next = now.children[letter] {
            now = next
        } else {
            break
        }
        if now.isEnd && index == str.count - 1 {
            answer += 1
        }
    }
}

print(answer)

이 글을 참고하여 Trie 자료구조를 구현하였다. 처음에는 아무 생각 없이 트라이의 노드를 Struct로 구현하려고 했는데 생각해보니 Struct는 값 타입이라 노드들을 연결할 수가 없었다..

제출하자마자 시간초과가 떠서 해결은 못했지만 그래도 트라이를 직접 구현해보고 Struct랑 Class의 차이를 다시 한 번 떠올릴 수 있었던 문제였다. ^__^..

Set을 이용한 풀이

let input = readLine()!.split(separator: " ").map { Int(String($0))! }
let (N, M) = (input[0], input[1])
var inputSet = Set<String>()

// 집합 S에 N개 문자열 삽입
for _ in 0..<N {
    let input = readLine()!
    inputSet.insert(input)
}

// M개의 문자열 탐색
var answer = 0

for _ in 0..<M {
    let input = readLine()!
    if inputSet.contains(input) {
        answer += 1
    }
}

print(answer)

간단하게 Set을 사용해서 풀어보니 통과가 됐다.