[백준 1141] 접두사 (Swift)

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

 

문자열 & 정렬

 

문자열들의 배열이 주어지고, 서로가 서로의 접두사가 아닌 부분집합의 최대 크기를 출력하는 문제

 

접근방법

 

처음에는 DFS로 가능한 부분집합을 모두 구하는 식으로 했다가 시간초과났다;ㅎ

알고리즘 분류를 보니까 정렬이라길래,,

문자열을 정렬해두고, 맨 위부터 본인보다 문자열이 큰(길이&알파벳순) 문자열에 대해서 본인이 그 문자열의 접두사면

본인을 부분집합에 포함시키지 않도록해서 result를 n에서 1씩 줄여나갔다.

 

따지고 보면, 알파벳순 & 길이순 으로 나열되어있는 문자열에서 내가 바로 다음 문자열의 접두사라면

내가 그 다음 문자열의 접두사일 확률도 높아진다.

그리고 그렇지 않더라도 내가 들어가면 그 다음 문자열과 나 중 하나는 빠져야 접두사X 집합이기 때문에

내가 빠지는게 필수적임(내가 빠지는게 내 다음 문자열이 빠지는 것보다 이득이다. 그 다음 문자열(i+1)은 그 다음 문자열(i+2)의 접두사일거라는 보장이 없으니까)

ex. a, ab, ac 라면 a가 ab의 접두사이니까 a를 빼면 ab,ac는 접두사 X 부분집합일 수 있다.

그치만 ab를 빼면, a, ac는 a가 ac의 접두사이므로 ac or a 만 남아야 접두사 X 부분집합일 수 있다.

우리는 지금 접두사 X 집합의 최대 크기를 구하는 것이므로

a vs ab 에서 a를 빼는 것이 확률적으로 최대 크기를 만들 수 있는 데는 더 이득이다.

 

소스코드

import Foundation

func solution() -> Int {
    
    // input
    let n:Int = Int(readLine()!)!
    var words:[String] = []
    for _ in 0..<n {
        words.append(readLine()!)
    }
    
    // process
    var result = n
    words.sort()
    
    for (i,word) in words.enumerated() {
        for j in i+1..<n {
            if words[j].starts(with: word) {
                result -= 1
                break
            }
        }
    }
    
    return result
    
}


print(solution())