문제 링크 http://icpc.me/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 트라이를 이용하여 풀 수 있다. 트라이에 전화번호를 넣는 과정에서 prefix가 똑같은 문자열을 발견하면 NO를 출력하면 된다. cf) new Trie()를 하여 동적 할당을 하는 것보다 전역 변수로 Trie를 많이 만들어 할당해주는 방식이 더 빠르기 때문에 아래와 같이 구현했다. 코드 #include struct Trie; Trie* new_trie(); struct Trie { int..

문제 링크 https://www.acmicpc.net/problem/5670 풀이 트라이를 이용하여 풀이할 수 있다. 어느 지점까지 입력하였을 때 나올 수 있는 경우의 수가 1인 경우 자동으로 입력을 해줘야 한다. 그러기 위해서 자식 노드의 수가 1개인 경우에 자동 입력을 해야 한다. 또한 hello hell와 같이 문자열의 앞부분이 동일한 경우에 hello를 입력하기 위해서는 hell을 입력하고 o를 한번 더 입력해야 한다. 이 경우는 자식 노드가 1개이며 문자열이 끝나는 경우 한번 더 입력하게 한다. Trie 구조체의 멤버로 Trie *nxt[26]으로 한번 구현하고 최적화를 위해 map으로 한번 더 구현했다. 코드 최적화x #include #include struct Trie { bool finis..

문제 링크 https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 풀이 trie를 이용하여 풀이할 수 있다. trie를 구현할때 string을 인덱스로 하고 값은 Node구조체로 하기 위해 map을 이용한다. 코드 #include #include #include #include using namespace std; struct Node { map child; }; void insert(Node &node, vector &arr, int ..