Funcia
Lv.1greedysortingtwo-pointers

구명보트

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

무인도에 갇힌 사람들을 구명보트로 구출하려고 합니다. 사람들의 몸무게가 배열 people로 주어집니다.

구명보트 하나에는 최대 두 명까지 탈 수 있고, 탄 사람들의 몸무게 합이 limit 이하여야 합니다. 구명보트는 몇 대든 쓸 수 있습니다.

모든 사람을 구출하는 데 필요한 구명보트 수의 최솟값을 반환하세요.

입출력 예

peoplelimitresult
[70, 50, 80, 50]1003
[70, 80, 50]1003
[30, 40, 50, 60]1002

입출력 예 설명

예 1 — 50과 50이 함께 타고, 70과 80은 각자 탑니다.

예 2 — 어떤 두 사람도 함께 탈 수 없습니다.

예 3 — (40, 60)과 (30, 50)으로 나눠 타면 두 대면 됩니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(people: int[], limit: int) → int

제한 사항

  • 1≤1 \le people.length ≤200,000\le 200{,}000
  • 1≤1 \le people[i] ≤\le limit ≤1,000,000\le 1{,}000{,}000

기대 복잡도

시간
O(N log N)
공간
O(1)

입출력 예

peoplelimit기대 출력
[70,50,80,50]1003
[70,80,50]1003
[30,40,50,60]1002

힌트

힌트

가장 무거운 사람은 어차피 보트 하나를 차지합니다. 이 사람과 함께 탈 사람으로는 가장 가벼운 사람을 고르는 것이 가장 유리합니다. 가장 가벼운 사람과도 못 탄다면 누구와도 못 타고, 함께 탈 수 있다면 가벼운 사람을 여기에 쓰는 것이 손해가 없기 때문입니다.

몸무게를 정렬하고 양 끝에서 포인터 두 개를 좁혀 오면 됩니다(투 포인터).

복잡도 목표

사람마다 남은 사람 전체를 훑어 짝을 찾으면 O(N2)O(N^2)이 되어 효율성 테스트에서 시간 초과가 납니다. 정렬 후 O(N)O(N)으로 짝을 지어야 합니다.

언어별 시간 제한

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

테스트 그룹

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

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