[백준/1141] 접두사

1. 문제

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

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

2. 입력

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

3. 코드

import sys
sys.stdin = open('input.txt')

n = int(input())
lst = [input() for _ in range(n)]
lst.sort() # 정렬하면 시간이 더 줄겠죠?
excep = lst[:] # 접두사인 단어는 삭제할 예정

for idx, test in enumerate(lst):
    for temp in lst[idx:]: # test접두사인가? / 비교대상 temp
        # test랑 temp가 동일한 애일때 검사 안함(test != temp)
        # 근데 본인아닌데 동일한 애도 검사를 피해가기때문에 밑에서 set해준다.) 
		# 비교대상 temp를 test접두사길이까지 잘라서 비교해보고 같으면 제거
        if test != temp and test == temp[:len(test)]: 
            excep.remove(test)
            break
            
# 동일한 단어는 제거
print(len(set(excep)))