알고리즘 문제/Leetcode
[Leetcode] 881. Boats to Save People
햄과함께
2023. 4. 7. 19:12
320x100
문제 : https://leetcode.com/problems/boats-to-save-people/description/
people이라는 배열이 주어지는데, people[i]는 i번째 사람의 몸무게를 나타냅니다.
그리고 무게 제한이 limit인 무수히 많은 보트가 있습니다.
각 보트는 최대 limit 무게까지 운반할 수 있으며, 최대 두 사람이 탈 수 있으며 두 사람의 무게 합이 limit 이하여야 합니다.
주어진 모든 사람을 운반하기 위해 필요한 최소 보트 수를 구하세요.
한 번에 두 명이 탈 수 있습니다. 투포인터로 해결할 수 있습니다.
먼저 people 배열을 오름차순 정렬합니다. 왼쪽부터 탐색하는 left 인덱스, 오른쪽부터 탐색하는 right 인덱스를 준비합니다.
만약 한 보트에 가장 무거운 사람(people[right])이 탔을 때, 가장 가벼운 사람(people[left])이 같이 탈 수 없다면 가장 무거운 사람은 혼자 타야 합니다.
즉, 남아있는 사람들 중 가장 무거운 사람과 가장 가벼운 사람이 함께 보트에 탈 수 있다면 (people[left] + people[right] <= limit) 같이 탑승하고, 불가능하다면 가장 무거운 사람만 보트에 탑승합니다.
이와 같은 방법으로 모든 사람들을 보트에 태웠을 때, 보트 수가 정답이 됩니다.
시간복잡도는 O(N).
320x100