2990번 - 단어 검색 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 128 MB | 665 | 126 | 86 | 23.118% |
문제
단어가 N개 있는 데이터베이스가 있다.
이 데이터베이스에서 어떤 단어를 찾을 때 사용하는 알고리즘은 상당히 원시적이다.
이 알고리즘은 단어 W와 데이터베이스에 있는 단어를 하나씩 비교한다. 단어를 비교할 때는, 각 단어의 가장 앞에서부터 다른 문자가 나오거나, 한 단어의 끝이 나올 때 까지 하나씩 비교한다. 만약, 단어 W를 찾으면 이 알고리즘은 그 즉시 종료된다.
단어의 길이는 단어를 검색하기 전에 알 수 없으므로, 마지막 글자도 비교를 해야 단어가 끝났다는 것을 알게 된다. 즉, abc와 abcd가 있을 때, abc의 4번째 글자와 abcd의 4번째 글자를 비교할 때 단어가 서로 다르다는 것을 알 수 있는 것이다. 마찬가지로 단어가 같은 것도 마지막 글자 다음 글자를 비교해야 알 수 있다. abc와 abc가 있을 때, abc의 4번째 글자와 abc의 4번째 글자가 모두 없는 것으로 같으므로 단어를 찾았다는 뜻이다.
단어 목록이 주어지고, 검색하려고 하는 단어가 주어졌을 때, 몇 번 비교만에 단어를 찾을 수 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 30,000)
다음 N개의 줄에는 데이터베이스에 있는 단어가 주어진다. 단어를 검색할 때, 입력으로 주어진 단어 순서를 그대로 사용해야 한다. 또한, 모든 단어는 다르다.
다음 줄에는 검색하려고 하는 단어의 개수 Q가 주어진다. (1 ≤ Q ≤ 30,000)
다음 Q개 줄에는 검색하려고 하는 단어가 주어진다.
모든 단어는 알파벳 소문자로 이루어져 있고, 길이는 30보다 작다.
출력
Q개 줄에 걸쳐, 각 단어를 검색하는데 필요한 비교의 수를 출력한다.
예제 입력 1
5 hobotnica robot hobi hobit robi 4 robi hobi hobit rakija
예제 출력 1
12 10 16 7
예제 입력 2
8 majmunica majmun majka malina malinska malo maleni malesnica 3 krampus malnar majmun
예제 출력 2
8 29 14
krampus를 검색하려면 데이터베이스에 있는 단어의 첫 번째 글자만 비교하면 되므로 8번만 비교하면 된다.
malnar를 검색하려면, 처음 3단어는 3번, 뒤의 5단어는 4번 검색하면 되므로 29번 비교하면 된다.
majmun을 검색하려면, 14번 검색하면 된다. 첫 번째 단어 "majmunica"와 7번 비교를 하고, 길이가 다르므로 다음 단어와 비교한다. 다음 단어에서 7번 비교를 하면 되므로 14번이다. 단어를 찾은 후에는 더이상 검색을 하지 않으므로 더 검색할 단어는 없다.
출처
Contest > Croatian Open Competition in Informatics > COCI 2007/2008 > Contest #5 6번
- 문제를 번역한 사람: baekjoon
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호