[백준/Swift] 1141번: 접두사

 

https://www.acmicpc.net/problem/1141

1141번: 접두사

 

사실 이 문제는 트리 문제를 풀어보기 위해 푼 문제였다. 그런데 도통 트리로는 어떻게 해야 할지 모르겠고 그냥 완탐으로 풀었다...

입력받은 문자열을 앞에서부터 뒤로 순회하면서 hasPrefix 메소드를 통해 이 단어를 접두사로 사용하는지 체크하고 접두사라면 answer에서 차감해 줬다. 왜냐면 부분 집합의 최대 크기를 구하는 게 목표인데 여기서 접두사가 되는 애들만 빼주면! 최대 크기가 되기 때문이다.

 

import Foundation

/*
 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합
 {hello}, {hello, goodbye, giant, hi}, {} 은 모두 접두사 X
 */

//input
let n = Int(readLine()!)!
var words = [String]()
var check = [Bool](repeating: false, count: n+1)
var answer = n

for _ in 0..<n {
    words.append(readLine()!)
}
words.sort()
for i in 0..<words.count {
    for j in i+1..<words.count {
        if words[j].hasPrefix(words[i]) {
            answer -= 1
            break
        }
    }
}
print(answer)

 

Tree 혹은 Trie 로도 풀 수 있는 것 같은데 꼭.. 공부를 더해서 그렇게 풀어보고 싶다! 다른 분의 코드를 보니까 그렇게 푸신 것 같은데 나는 12ms가 걸렸는데 그분은 8ms가 걸렸다! 더 공부를 해서 다시 풀어보자~