Funcia
Lv.3binary-searchstringtrie

접두사로 시작하는 단어 세기

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

검색창에 글자를 입력하면 "이 글자로 시작하는 단어가 몇 개 있는지"를 보여 주려고 합니다.

사전에 들어 있는 단어 목록 words와 입력 목록 queries가 주어집니다. 각 queries[j]에 대해, words 중 queries[j]로 시작하는 단어의 개수를 구해 순서대로 배열에 담아 반환하세요. 단어 자신과 같은 입력도 "그 단어로 시작한다"고 봅니다. words에 같은 단어가 여러 번 있으면 각각 따로 셉니다.

입출력 예

wordsqueriesresult
["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[]

제한 사항

  • 1≤N=1 \le N = words.length ≤100,000\le 100{,}000, 1≤Q=1 \le Q = queries.length ≤100,000\le 100{,}000
  • 모든 단어와 입력은 길이 1 이상이며 알파벳 소문자로만 이루어져 있습니다.
  • words의 길이 합 ≤106\le 10^6, queries의 길이 합 ≤106\le 10^6

기대 복잡도

시간
O(sum of lengths)
공간
O(sum of word lengths)

입출력 예

wordsqueries기대 출력
["apple","app","apply","bat","bath"]["app","ba","c","apple"][3,2,0,1]
["a","a","ab"]["a","ab","abc"][3,1,0]

힌트

힌트

질문마다 단어 전체를 훑으면 O(N⋅Q)O(N \cdot Q)번 비교하게 됩니다. 단어를 미리 정리해 두세요.

트라이(접두사 트리): 단어를 한 글자씩 따라 내려가며 노드를 만들고, 지나가는 모든 노드의 카운터를 1씩 올립니다. 그러면 어떤 노드의 카운터는 "그 노드까지의 글자로 시작하는 단어 수"가 됩니다. 질문은 글자를 따라 내려가다 길이 끊기면 0, 끝까지 가면 그 노드의 카운터가 답입니다.

다른 방법으로, 단어를 사전순 정렬해 두면 q로 시작하는 단어들은 정렬된 목록에서 한 구간을 이루므로 이분 탐색 두 번으로 개수를 셀 수도 있습니다.

복잡도 목표

질문마다 모든 단어를 확인하는 풀이는 효율성 테스트에서 시간 초과가 납니다. 트라이는 길이 합에 비례하는 시간이면 충분합니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)200 ms추정
C++ (GCC, gnu++23)200 ms도출됨
Python 3.131000 ms도출됨
Java 251506 ms도출됨
Kotlin 2.4 (JVM)1400 ms추정
C# 14 (.NET 10)1400 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample02입력·출력 공개
correctness4010판정만
performance604판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.