[BOJ-#1141] 접두사

문제

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

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

입력

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

출력

첫째 줄에 문제의 정답을 출력한다.

---

Code

Github 링크

import sys

input = sys.stdin.readline
test_case = int(input().rstrip())
list_ = []
# cnt = 0
cnt = test_case

for _  in range(test_case) :
    list_.append(input().rstrip())

list_.sort(key = lambda x : len(x))

for i in range(test_case) :
    for j in range(i+1, test_case) :
        if list_[i] == list_[j][:len(list_[i])] :
            cnt -= 1
            break
    
print(cnt)

코드 설명

import sys

input = sys.stdin.readline
test_case = int(input().rstrip())
list_ = []
# cnt = 0
cnt = test_case

for _  in range(test_case) :
    list_.append(input().rstrip())

빠른 입력을 받을 수 있도록 input을 선언하고 테스트 케이스와 집합을 받은 후 cnt를 테스트 케이스로 선언한다.

list_.sort(key = lambda x : len(x))

for i in range(test_case) :
    for j in range(i+1, test_case) :
        if list_[i] == list_[j][:len(list_[i])] :
            cnt -= 1
            break
    
print(cnt)

lambda를 이용해서 길이를 기준으로 집합을 정렬한다. 이후 테스트 케이스만큼, i 다음부터 끝까지 for문을 돌려서 접두사가 있을 경우 cnt를 하나 줄이는 방식으로 진행했다. 이때, 접두사에 해당되는 단어를 하나 발견했을 경우 그보다 더 긴 단어에 또 있을 수 있으므로 break를 걸어주는 것을 잊으면 안 된다.

---

리뷰

목요일에 풀고 일요일에 써서 기억이 잘 안 난다... 근데 수요일에 재형 오빠가 풀이했던 문제랑 비슷해서 비교적 쉽게 풀었던 기억이 난다. 그리고 sort 할 때 lambda를 이용해서 기준을 잡는 게 굉장히 중요하다고 생각하게 된 문제이다. 우와 쓰다가 뒤로가기 눌러서 혀 깨물 뻔했는데 다행히 임시 저장되어 있었다... 벨로그 굿