[정렬] 백준 #1141 접두사 - Python

🗂️ 문제

링크: https://www.acmicpc.net/problem/1141

1141번: 접두사

 

💡 접근법

접두사X 집합이란 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 집합을 말한다. 즉 전체 집합에서 다른 단어의 접두어가 되는 단어들 제외한 단어들의 개수를 구하는 문제이다.

 

리스트를 정렬하고 각각의 요소를 순회하면서 현재 문자열이 다음 문자열에 접두어가 되는지 확인한다. 여기서 문자열을 정렬했기 때문에 바로 다음 문자열이 접두어가 되는지 여부만 확인하면 된다.

또한 다른 단어의 접두어가 되는 단어는 다른 단어보다 크기가 작거나 같아야한다.

 

만약 현재 문자열이 다음 문자열의 접두어가 된다면 continue를 수행하고, 아닐 경우 cnt를 1 증가시킨다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
arr = [sys.stdin.readline().rstrip() for _ in range(N)]
arr.sort()

cnt = 1
for i in range(len(arr)-1):
    # 현재 단어의 길이가 다음 단어의 길이보다 같거나 작은지 확인하고 이를 만족할 경우 현재 단어가 다음 단어의 접두어에 해당하는지 확인한다.
    if len(arr[i]) <= len(arr[i+1]) and arr[i] == arr[i+1][:len(arr[i])]:
        continue

    cnt += 1

print(cnt)

 

✅ 정답 확인