8069 : 단어 탐색
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
알파벳 소문자로만 이루어진 $N$개의 단어로 구성된 사전이 주어집니다.
그 후 $M$개의 질의 단어가 주어질 때, 각 질의 단어가 사전에 존재하는지 여부를 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 30{,}000$
• 각 단어의 길이는 $1$ 이상 $30$ 이하의 알파벳 소문자입니다.
그 후 $M$개의 질의 단어가 주어질 때, 각 질의 단어가 사전에 존재하는지 여부를 판별하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 30{,}000$
• 각 단어의 길이는 $1$ 이상 $30$ 이하의 알파벳 소문자입니다.
입력 설명
첫째 줄에 사전에 등록된 단어 수 $N$과 확인할 질의 단어 수 $M$이 공백으로 구분되어 주어집니다. ($1 \le N, M \le 30{,}000$)
둘째 줄부터 $N$개의 줄에 걸쳐 사전 단어들이 한 줄에 하나씩 주어집니다.
그 다음 $M$개의 줄에 걸쳐 질의 단어들이 한 줄에 하나씩 주어집니다.
각 단어의 길이는 $1$ 이상 $30$ 이하의 알파벳 소문자입니다.
둘째 줄부터 $N$개의 줄에 걸쳐 사전 단어들이 한 줄에 하나씩 주어집니다.
그 다음 $M$개의 줄에 걸쳐 질의 단어들이 한 줄에 하나씩 주어집니다.
각 단어의 길이는 $1$ 이상 $30$ 이하의 알파벳 소문자입니다.
출력 설명
각 질의 단어에 대하여, 사전에 존재하면
1, 존재하지 않으면 0을 한 줄에 하나씩 순서대로 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4 4
apple
banana
app
cherry
apple
banan
cherry
ap
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
0
1
0도움
트라이(Trie) 구조를 이용해 단어들을 등록하고 검색하거나 해시 셋(Hash Set)을 활용하면 매우 빠르게 해결할 수 있습니다.