목록5052 (1)

개발자 노트

[백준]5052 전화번호목록

문제설명 트라이로 접근하는 것. 전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다. 접근 TRI 이용 완전탐색으로 접근하지 않는 이유 완전탐색으로 접근하면 시간복잡도는 엄청나다. 매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수) 따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다. tri접근시 공간복잡도 고려 0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000..
알고리즘 문제 풀이 2020. 3. 31. 00:40
Prev 1 Next