Funcia
Lv.1countinghashstring

글자로 단어 만들기

Memory limit
256 MB
Correctness time limit
10000 ms
Acceptance
100.0%
Solvers
1
0

대문자 문자열 S와 대문자 단어 배열 L이 주어집니다.

S의 각 글자는 한 번씩만 쓸 수 있습니다. L의 각 단어를 몇 번까지 만들 수 있는지 단어마다 독립적으로 계산하고, 그중 최댓값을 반환하세요.

"독립적으로"란, 한 단어를 만들 때 S 전체를 쓸 수 있다는 뜻입니다.

입출력 예

SLresult
"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

  • 1≤∣S∣≤200,0001 \le |S| \le 200{,}000
  • 1≤1 \le L.length ≤100\le 100
  • 각 단어의 길이는 1 이상 10 이하
  • S와 모든 단어는 대문자 A–Z 로만 이루어져 있습니다.

Expected complexity

Time
O(|S| + M*K)
Space
O(1)

Examples

SLExpected
"LILLYBILLYBOO"["BILL","MARIA","LILLY"]2
"AABB"["AB","AAB"]2
"ABC"["XYZ"]0

Hint

Hint

실제로 글자를 지워가며 만들어볼 필요가 없습니다. 글자별 개수만 알면 답이 나옵니다.

단어 쪽 글자도 개수를 세야 합니다. BILL에는 L이 두 번 들어가니까요. 각 글자에 대해

⌊S의 그 글자 개수단어의 그 글자 개수⌋\left\lfloor \frac{S \text{의 그 글자 개수}}{\text{단어의 그 글자 개수}} \right\rfloor

를 구하고, 그 최솟값이 그 단어를 만들 수 있는 횟수입니다. 가장 부족한 글자가 병목이 되는 구조입니다.

주의할 점 두 가지입니다.

  • 단어에 없는 글자는 필요 개수가 0이라 나누면 0으로 나누는 오류가 납니다. 등장하는 글자만 보세요.
  • 최솟값을 구하니 초깃값을 0이 아니라 아주 큰 값으로 두세요.

글자가 A–Z 로 고정이니 해시맵 대신 크기 26 배열과 c - 'A' 를 쓰면 더 빠르고 짧습니다.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251400 msestimated
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1000 msderived

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.