1141번: 접두사

문제 출처 : https://www.acmicpc.net/problem/1141

1141번: 접두사

언어 : Kotlin

 

문제 설명 :

접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.

단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

 

입력 :

첫째 줄에 단어의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 단어가 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 최대 50이다. 집합에는 같은 단어가 두 번 이상 있을 수 있다.

 

출력 :

첫째 줄에 문제의 정답을 출력한다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

입출력 예 :

입력	출력
6 hello hi h run rerun running	4
6 a b cba cbc cbb ccc	6
6 a ab abc abcd abcde abcdef	1
3 topcoder topcoder topcoding	2

 

풀이 : 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    var result = 0
    val n = readLine().toInt()
    val list = ArrayList<String>()
    repeat(n) {
        list += readLine()
    }

    list.sortBy { it.length }
    for (i in list.indices) {
        var check = true
        for (j in i + 1 until list.size) {
            if (list[j].startsWith(list[i])) {
                check = false
                break
            }
        }

        if (check) result++
    }

    bw.write("$result")
    bw.flush()
    bw.close()
}