[Programmers] 구명보트 JAVA

반응형

728x90

[Programmers] 구명보트 - LV 2

---

접근

• 그리디
• 투 포인터

---

풀이

무인도에 갇힌 사람들이 구명보트를 통해 탈출하는 문제로 구명보트에는 무게 제한이 있기 때문에 무게 제한을 만족하며 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 구하는 문제이다. 그런데 구명보트는 작기 때문에 한 번에 최대 2명씩 밖에 탈 수 없다.  2명, 2명이 한 보트당 최대 인원이다. 이 2명이라는 내용을 제대로 읽지 않아 불 필요하게 복잡한 코드와 함께 통과에 실패했다. 보트의 제한 무게가 40kg 이상 240kg 이하이기 때문에 무게만 맞춘다면 몇 사람이 타던 상관이 없는 줄 알고 풀었는데 보트에는 2명밖에 태울 수 없었다. 사실 너무 간단한 문제였다.

    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
            
        int left = 0;
        int right = people.length - 1;

그리디 카테고리의 문제였지만 그리디보단 투 포인터에 좀 더 집중되는 문제인 거 같다. 그리디로 풀기 위해 투 포인터를 사용하는 거지만 어쨌든 사람들을 몸무게 순으로 정렬해주어야 한다. 두 개의 포인터를 사용해 정렬된 사람들을 기준으로 가벼운 사람 1명 + 무거운 사람 1명의 조합으로 보트에 태우게 된다. 두 명의 무게가 보트의 제한 무게를 넘어가게 된다면 무거운 사람 1명을 태우게 되고 넘어가지 않는다면 두 명을 모두 태우는 것이다. 가벼운 사람을 우선으로 태우게 된다면 무거운 사람만 남아 가벼운 사람 2명이 탈 수 있던 보트를 무거운 사람 1명이 타고 가야 하므로 무거운 사람을 우선으로 태운다.

	while(left <= right) {
            if(people[left] + people[right] <= limit){
                left++;
                right--;
            } else {
                right--;
            } 
            answer++;
        }
        
        return answer;

이 과정을 모든 사람을 다 태울 때까지 반복하면 된다.

---

전체 코드

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
            
        int left = 0;
        int right = people.length - 1;
                
        while(left <= right) {
            if(people[left] + people[right] <= limit){
                left++;
                right--;
            } else {
                right--;
            } 
            answer++;
        }
        
        return answer;
    }
}