⚠️ 문제
https://www.acmicpc.net/problem/1141
🔐 풀이
문제에서 접두사X 집합이란 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 집합입니다.
접두사X 집합인 부분집합의 최대 크기는 곧 전체 집합에서 다른 단어의 접두어가 되는 단어만 제외한 집합이 됩니다.
또, A 단어가 B 단어의 접두어가 되기 위해서는 A 단어의 길이가 B 단어의 길이보다 짧거나 같아야 합니다.
따라서 단어 배열을 우선 단어의 길이가 짧은 순으로 정렬해주고, 자신보다 길이가 길거나 같은 단어들과 비교하며 접두어가 될 수 있는지 확인하고 접두어가 될 때만 집합에서 제외(개수 -1)하면 됩니다.
🧑🏻💻 코드
import sys
N = int(sys.stdin.readline().rstrip())
arr = []
for _ in range(N):
arr.append(sys.stdin.readline().rstrip())
# 문자열 길이 짧은 순으로 정렬
arr.sort(key=lambda x: len(x))
answer = len(arr)
for i in range(len(arr)):
isPrefix = False
# 더 긴 문자열 중에서 비교
for j in range(i+1, len(arr)):
if arr[i] == arr[j][:len(arr[i])]:
isPrefix = True
break
# 접두어가 되면 집합에서 제외
if isPrefix:
answer -= 1
print(answer)