BOJ 5052 - 전화번호 목록

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

문제

한 문자열이 다른 문자열의 접두어(prefix)이면 NO, 그런 경우가 없으면 YES를 출력하는 문제이다.

풀이 1 (정렬)

모든 문자열을 사전순으로 정렬하면, 접두어가 겹치는 문자열끼리 붙어있다.

어떤 문자열이 직전 문자열의 부분 문자열인지 확인하면 된다.

시간 복잡도는 정렬 + 부분 문자열 확인 시간만큼이므로, \(O(nlogn + n|s_{max}|)\)

코드 1 (정렬)

풀이 2 (트라이; Trie)

분류에 트라이가 있기도 하고, 트라이를 한번도 구현해본 적 없어서 트라이로 풀어봤다.

문자열을 하나씩 확인하며 트라이를 만들어간다.

어떤 문자열이 끊긴 지점에 "이 곳이 하나의 단어였다"로 리프 표시를 해두고 넘어간다.

다음에 트라이를 만드는 과정에서, 문자열 끝이 아닌 데 이 부분이 발견된다면 부분 문자열이 있었다는 뜻이다.

코드 2 (트라이; Trie)