[BOJ] 5052: 전화번호 목록

 

전화번호 n개에 대해 서로 접두사 관계인게 존재하는지 찾는 문제이다.

 

전화번호의 길이는 O(1)이고 완전탐색을 통해 찾으면 O(n^2)이 되기 떄문에 더 빠른 알고리즘을 찾아야 한다.

 

문제를 풀고 검색을 해보니 트라이라는 자료구조, 또 문자열 배열 전체를 정렬해서 인접 문자열끼리만 확인하는 간단한 방법이 있었다. 

 

나는 문제를 풀긴 풀었는데 뭔가 빙빙(?) 돌아갔다.

 

풀이

나는 일단 가능한 케이스를 모두 뒤져보는 완전탐색으로 풀었다.

 

1. 문자열을 길이별로 나눈 후 정렬한다. ( O(nlogn) 소요 )

ex ) LIST[2] 에는 길이 2인 문자열들을 정렬하여 저장

 

2.  1<=i<j<=10 인 순서쌍 (i,j) 에 대해 

LIST[i]에 있는 문자열들을 순회하며 LIST[i]의 원소가 LIST[j]의 원소 중 접두사가 가능한 게 있는지 찾는다.

 

이 때 LIST[i]의 크기는 N이므로 LIST[i]의 문자열 순회는 O(n) 이 소요되고,

LIST[j]는 정렬되어있는 상태이므로 LIST[i]의 원소를 LIST[j]에서 찾는것은 O(logn)이 소요된다. 

 

따라서 (i,j)에 대해 수행하는 연산은 총 O(nlogn)이 소요된다.

또한 가능한 순서쌍 (i,j)는 문자열의 길이가 제한되어있기 때문에 O(1)이기 때문에 ( 최대 가능한 경우의 수는 55이다. )

모든 원소를 순회하며 탐색하는데 O(nlogn)이 소요된다.

 

정렬에 O(nlogn), 탐색에 O(nlogn)이 소요되므로 총 O(nlogn)에 문제를 풀 수 있다.

 

 

이렇게 풀긴 풀었는데 뭔가 엄청 간단한 풀이들이 있고,

트라이 라는 자료구조도 알게 되었음. 끝 !

 

또 파이썬에서 input()으로 받으니 시간초과가 뜬다. 메모메모