문제

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

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

# 1141
import sys
input = lambda : sys.stdin.readline().strip()

n = int(input())
input_list = []

for _ in range(n):
    input_str = input()
    len_str = len(input_str)
    check = True
    
    for ls in input_list:
        len_ls = len(ls)
        if len_str < len_ls:
            if input_str == ls[:len_str]:
                check = False
                break
        else:
            if ls == input_str[:len_ls]:
                input_list.remove(ls)
                
    if check:
        input_list.append(input_str)
        
print(len(input_list))

백준 1141 접두사