접두사로 시작하는 단어 세기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
검색창에 글자를 입력하면 "이 글자로 시작하는 단어가 몇 개 있는지"를 보여 주려고 합니다.
사전에 들어 있는 단어 목록 words와 입력 목록 queries가 주어집니다. 각 queries[j]에 대해,
words 중 queries[j]로 시작하는 단어의 개수를 구해 순서대로 배열에 담아 반환하세요.
단어 자신과 같은 입력도 "그 단어로 시작한다"고 봅니다. words에 같은 단어가 여러 번 있으면 각각 따로 셉니다.
입출력 예
| words | queries | result |
|---|---|---|
["apple", "app", "apply", "bat", "bath"] | ["app", "ba", "c", "apple"] | [3, 2, 0, 1] |
["a", "a", "ab"] | ["a", "ab", "abc"] | [3, 1, 0] |
입출력 예 설명
예 1 — "app"으로 시작하는 단어는 apple, app, apply의 3개입니다. "ba"는 bat, bath, "c"로 시작하는 단어는 없습니다.
예 2 — "a"가 두 번 들어 있으므로 따로 셉니다. "abc"는 "ab"보다 길어서 "ab"는 "abc"로 시작하지 않습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(words: string[], queries: string[]) → int[]
제한 사항
-
words.length,queries.length - 모든 단어와 입력은 길이 1 이상이며 알파벳 소문자로만 이루어져 있습니다.
words의 길이 합 ,queries의 길이 합
기대 복잡도
- 시간
- O(sum of lengths)
- 공간
- O(sum of word lengths)
입출력 예
| words | queries | 기대 출력 |
|---|---|---|
["apple","app","apply","bat","bath"] | ["app","ba","c","apple"] | [3,2,0,1] |
["a","a","ab"] | ["a","ab","abc"] | [3,1,0] |
힌트
힌트
질문마다 단어 전체를 훑으면 번 비교하게 됩니다. 단어를 미리 정리해 두세요.
트라이(접두사 트리): 단어를 한 글자씩 따라 내려가며 노드를 만들고, 지나가는 모든 노드의 카운터를 1씩 올립니다.
그러면 어떤 노드의 카운터는 "그 노드까지의 글자로 시작하는 단어 수"가 됩니다.
질문은 글자를 따라 내려가다 길이 끊기면 0, 끝까지 가면 그 노드의 카운터가 답입니다.
다른 방법으로, 단어를 사전순 정렬해 두면 q로 시작하는 단어들은 정렬된 목록에서 한 구간을 이루므로
이분 탐색 두 번으로 개수를 셀 수도 있습니다.
복잡도 목표
질문마다 모든 단어를 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 트라이는 길이 합에 비례하는 시간이면 충분합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1506 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 2 | 입력·출력 공개 |
| correctness | 40 | 10 | 판정만 |
| performance | 60 | 4 | 판정만 |