백준 5052. 전화번호 목록

티스토리 뷰

tose33 2022. 11. 28. 15:03

5052번: 전화번호 목록

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가

www.acmicpc.net

문자열을 저장하는 트라이 자료구조를 이용한 문제.

트라이 자료구조

https://yabmoons.tistory.com/379 [ 자료구조 트라이(TRIE) ] 개념과 구현방법 (C++) 이번 글에서는 자료구조 트라이(TRIE) 에 대해서 알아보자. 1. 트라이 (TRIE) ?? 먼저 '트라이'가 무엇인지에 대해서 부터 알아

tose33.tistory.com

트라이 자료구조에 문자를 Insert 하다가, bool finish 가 true를 만나면 이미 해당 문자열이 존재하는 것이기 때문에 해당 번호는 일관성이 없다고 할 수 있기 때문에 더 이상 탐색을 그만두고 일관성 없음을 표시하면 된다.

주의할점은 이런식으로 문자열을 insert 하면서 중복검색까지 할 경우, 문자열을 문자열 길이 기준 오름차순 정렬하고 트라이 자료구조에 넣어야 한다.

그렇지 않으면 만약 다음 두 번호를 입력한다고 하면 "11111", "1"

"11111"가 먼저 트라이 자료구조에 insert 된다.

그 후 "1"을 Insert하면 "1"은 크기가 1이기 때문에 기존 "11111"의 첫 노드까지만 방문하고 종료된다.

따라서 문자열의 끝을 뜻하는 finish=true 를 못만나고 종료되기 때문에 "11111", "1"은 일관성이 없음에도 불구하고 일관성 있음이 출력되버린다.

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함