[백준 1141번] 파이썬 - 접두사

백준 1141_접두사

시간제한 2초, 메모리제한 128MB

조건

• 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다.
• 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, gig, g}는 접두사X 집합이 아니다.
• 단어 N개로 이루어진 집합이 주어질 때, 접두사X 집합인 부분집합의 최대 크기를 출력하시오.

입력

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

접근 방법

• 다른 단어의 접두사가 되는 단어는 항상 길이가 더 짧거나 같다.
• 반복문을 통해 현재 단어와 그 외 단어들을 확인한다.
• 현재 단어보다 길이가 긴 단어들을 확인하고 현재 단어가 다른 단어의 접두사인지 확인한다.
• 현재 단어가 접두사가 아니라면 res를 카운트한다.

import sys  

n = int(sys.stdin.readline())  
words = [(sys.stdin.readline()).rstrip() for _ in range(n)]  

# 다른단어의 접두사가 되는 단어는 항상 다른단어보다 크기가 작거나 같다.  
# 따라서 문자열의 길이가 짧은 순서대로 정렬을 하고, 자기 위치보다 뒤에있는 단어와만 비교한다.  
words.sort(key=len)  
res = 0  

# 반복문을 통해 단어를 확인  
for i in range(n):  
    flag = False  
    # 현재 단어보다 길이가 긴 단어를 확인  
    for j in range(i + 1, n):  
        # 현재 단어가 접두사인지 확인  
        if words[i] == words[j][0:len(words[i])]:  
            flag = True  
            break  
    # 현재 단어가 접두사가 아니라면 res 카운트  
    if not flag:  
        res += 1  

print(res)