Lv.1countinghashstring
글자로 단어 만들기
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Acceptance
- 100.0%
- Solvers
- 1
대문자 문자열 S와 대문자 단어 배열 L이 주어집니다.
S의 각 글자는 한 번씩만 쓸 수 있습니다. L의 각 단어를 몇 번까지 만들 수 있는지 단어마다 독립적으로 계산하고, 그중 최댓값을 반환하세요.
"독립적으로"란, 한 단어를 만들 때 S 전체를 쓸 수 있다는 뜻입니다.
입출력 예
| S | L | result |
|---|---|---|
"LILLYBILLYBOO" | ["BILL", "MARIA", "LILLY"] | 2 |
"AABB" | ["AB", "AAB"] | 2 |
"ABC" | ["XYZ"] | 0 |
입출력 예 설명
예 1 — BILL은 2번, MARIA는 0번(M이 없음), LILLY는 1번 만들 수 있어 최댓값은 2입니다.
예 2 — AB는 2번, AAB는 1번 만들 수 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
Function signature
solution(S: string, L: string[]) → int
Constraints
-
L.length - 각 단어의 길이는 1 이상 10 이하
S와 모든 단어는 대문자A–Z로만 이루어져 있습니다.
Expected complexity
- Time
- O(|S| + M*K)
- Space
- O(1)
Examples
| S | L | Expected |
|---|---|---|
"LILLYBILLYBOO" | ["BILL","MARIA","LILLY"] | 2 |
"AABB" | ["AB","AAB"] | 2 |
"ABC" | ["XYZ"] | 0 |
Hint
Hint
실제로 글자를 지워가며 만들어볼 필요가 없습니다. 글자별 개수만 알면 답이 나옵니다.
단어 쪽 글자도 개수를 세야 합니다. BILL에는 L이 두 번 들어가니까요. 각 글자에 대해
를 구하고, 그 최솟값이 그 단어를 만들 수 있는 횟수입니다. 가장 부족한 글자가 병목이 되는 구조입니다.
주의할 점 두 가지입니다.
- 단어에 없는 글자는 필요 개수가 0이라 나누면 0으로 나누는 오류가 납니다. 등장하는 글자만 보세요.
- 최솟값을 구하니 초깃값을
0이 아니라 아주 큰 값으로 두세요.
글자가 A–Z 로 고정이니 해시맵 대신 크기 26 배열과 c - 'A' 를 쓰면 더 빠르고 짧습니다.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1400 ms | estimated |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1000 ms | derived |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 4 | verdict only |