[파이썬(Python)] 백준 1141번 : 접두사

문제

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

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

입력

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

풀이

N = int(input()) word = [] res = 0 for _ in range(N):     W = input()     word.append(W) word.sort(key=len) #단어 길이 순서대로 정렬  # print(word) for i in range(N):     cword = word[i]     flag = False #접두사일 경우의 flag          for j in range(i+1, N): #현재 단어보다 긴 단어와 비교         if cword == word[j][0:len(cword)]:             flag = True             break     if not flag: # 접두사가 아니면 res = res + 1         res += 1 print(res)

=> 한마디로 문자를 길이 순서대로 정렬했을 때, 앞의 단어가 현재 단어의 앞에 존재하면 카운트 되지 않고, 앞의 단어가 현재 단어의 앞에 존재하지 않으면(예를 들면, hel -> hello 면 현재 hello를 받을때 앞의 단어 hel이 hello 단어에 존재하게 됨) 카운트 되어 집합을 이루게 된다.

=> 따라서 먼저 입력한 단어들을 모두 길이 순서대로 정렬한다. (key = len)을 하여 sort한다.

현재 단어를 cword로 받고 접두사가 되는지 안되는지의 판단을 위해 BOOL값인 flag를 지정한다.(초기값은 False)

현재 가리키는 단어 cword가 다음 단어(순서상 cword보다 긴 단어)들에 속해 있는지 확인한다.

(반복문을 통해서 나머지 단어들과 비교한다.)

있다면 flag를 True로 하여 종료하고 존재하지 않으면 flag는 False로 하여 카운트 한다.