Lv.1countinghashstring
글자로 단어 만들기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 정답률
- 100.0%
- 푼 사람
- 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번 만들 수 있습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(S: string, L: string[]) → int
제한 사항
-
L.length - 각 단어의 길이는 1 이상 10 이하
S와 모든 단어는 대문자A–Z로만 이루어져 있습니다.
기대 복잡도
- 시간
- O(|S| + M*K)
- 공간
- O(1)
입출력 예
| S | L | 기대 출력 |
|---|---|---|
"LILLYBILLYBOO" | ["BILL","MARIA","LILLY"] | 2 |
"AABB" | ["AB","AAB"] | 2 |
"ABC" | ["XYZ"] | 0 |
힌트
힌트
실제로 글자를 지워가며 만들어볼 필요가 없습니다. 글자별 개수만 알면 답이 나옵니다.
단어 쪽 글자도 개수를 세야 합니다. BILL에는 L이 두 번 들어가니까요. 각 글자에 대해
를 구하고, 그 최솟값이 그 단어를 만들 수 있는 횟수입니다. 가장 부족한 글자가 병목이 되는 구조입니다.
주의할 점 두 가지입니다.
- 단어에 없는 글자는 필요 개수가 0이라 나누면 0으로 나누는 오류가 납니다. 등장하는 글자만 보세요.
- 최솟값을 구하니 초깃값을
0이 아니라 아주 큰 값으로 두세요.
글자가 A–Z 로 고정이니 해시맵 대신 크기 26 배열과 c - 'A' 를 쓰면 더 빠르고 짧습니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1400 ms | 추정 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1000 ms | 도출됨 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 4 | 판정만 |