programmer life guidance 101

www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 (하단 참고) 1536 MB 4468 2360 1563 55.327% 문제 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M..

> 트라이(Trie) 여튼 또 문자열인데, 이번엔 매칭 문제가 아니라 여러 문자열을 저장하는 자료구조를 소개해드릴 겁니다. 바로 트라이(Trie)인데, 트리와 굉장히 스펠링이 비슷하면서 트리와도 유사합니다. 아니, 아예 트리의 한 종류라고 해도 될 겁니다. 래딕스 트리(radix tree)나 접두사 트리(prefix tree)라고도 합니다. 예를 들어 {"he", "she", "her", "him", "show"}라는 문자열 집합이 있다면, 그들을 담고 있는 트라이는 그림과 같습니다. 빨간색 겹선 노드가 여기서 끝나는 문자열이 있다는 뜻으로, output이 있다고 하거나 final state, accepting node라고도 하는 등... 그런 의미가 있습니다. 왜 트라이의 별칭 중 접두사 트리라는 것이..