Lv.1greedysortingtwo-pointers
쿠키 나눠주기
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
아이들에게 쿠키를 나눠 주려고 합니다. 아이 i는 크기가 greed[i] 이상인 쿠키를 받아야 만족하고, 쿠키 j의 크기는 cookies[j]입니다.
아이 한 명에게는 쿠키를 최대 한 개만 줄 수 있고, 쿠키 하나는 한 아이에게만 줄 수 있습니다. 쿠키가 남거나 쿠키를 받지 못하는 아이가 있어도 괜찮습니다.
만족하는 아이 수의 최댓값을 반환하세요.
입출력 예
| greed | cookies | result |
|---|---|---|
[1, 2, 3] | [1, 1] | 1 |
[1, 2] | [1, 2, 3] | 2 |
[5, 10, 2, 8] | [3, 9, 6, 1, 4] | 3 |
입출력 예 설명
예 1 — 크기 1인 쿠키 두 개로는 greed가 1인 아이 한 명만 만족시킬 수 있습니다.
예 2 — 크기 1, 2 쿠키를 각각 두 아이에게 주면 둘 다 만족합니다.
예 3 — greed가 2, 5, 8인 아이에게 크기 3, 6, 9 쿠키를 주면 세 명이 만족합니다. greed가 10인 아이를 만족시킬 쿠키는 없습니다.
효율성
이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.
함수 시그니처
solution(greed: int[], cookies: int[]) → int
제한 사항
-
greed.length -
cookies.length -
greed[i],cookies[j]
기대 복잡도
- 시간
- O(N log N + M log M)
- 공간
- O(1)
입출력 예
| greed | cookies | 기대 출력 |
|---|---|---|
[1,2,3] | [1,1] | 1 |
[1,2] | [1,2,3] | 2 |
[5,10,2,8] | [3,9,6,1,4] | 3 |
힌트
힌트
욕심이 가장 적은 아이부터 생각해 보세요. 그 아이를 만족시킬 수 있는 쿠키 중 가장 작은 것을 주는 것이 손해가 없습니다. 더 큰 쿠키는 더 욕심 많은 아이를 위해 아껴 둘 수 있기 때문입니다.
두 배열을 모두 정렬한 뒤, 쿠키를 작은 것부터 보면서 "지금 쿠키가 아직 만족하지 못한 가장 덜 욕심 많은 아이를 만족시키는가?"만 확인하면 됩니다(투 포인터).
복잡도 목표
아이마다 쿠키 배열을 처음부터 다시 훑어 쓸 수 있는 쿠키를 찾으면 이 되어 효율성 테스트에서 시간 초과가 납니다. 정렬 후 한 번 훑는 이 필요합니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | 추정 |
| C++ (GCC, gnu++23) | 200 ms | 도출됨 |
| Python 3.13 | 1000 ms | 도출됨 |
| Java 25 | 1404 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1400 ms | 추정 |
| C# 14 (.NET 10) | 1400 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 11 | 판정만 |
| performance | 60 | 3 | 판정만 |