Lv.2 : 구명보트

👉 문제링크

프로그래머스

---

---

🔸 문제 분석 🔸

• 사람을 무게 제한이 limit인 구명 보트로 각각 최대 2명씩 구조할 수 있다.
• 모든 사람을 구하기 위한 구명보트 개수의 최솟값을 반환한다.

🔸 문제 풀이 🔸

• 그리디적으로 접근한다.
• 사람들의 몸무게를 정렬한다.
  • 오름차순으로 정렬했을때 가장 무거운 사람이 오른쪽 끝에 있다.
  • 가장 무거운 사람을 옮길 때 가장 가벼운 사람과 같이 탈 수 없다면, 혼자만 탈 수 있다.
  • 가장 무거운 사람 + 가장 가벼운 사람 둘이 탈 수 있으면 타고 탈출하면 된다.

---

🔸 코드 🔸

import java.util.Arrays;

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

🔸 코드 해석 🔸

• 사람들의 몸무게 배열 people을 오름차순 정렬한다.
• left는 왼쪽끝 인덱스, right는 오른쪽끝 인덱스로 시작한다.
• 두 인덱스가 같아 질 때까지 계산을 반복한다.
  • 두 사람이 모두 탈 수 있으면 둘 다 타므로, left는 +1, right는 -1한다.
  • 두 사람이 모두 탈 수 없으면 무거운 사람만 타야되므로, right만 -1한다.
  • 반복 한 번에 보트 하나가 출발하므로, answer +1 한다.

---

🔸 end 🔸

• 처음에는 한 보트에 사람들이 최적으로 타야된다고 생각했다.
  • 남은 무게 공간이 최소가 되도록 무거운 쪽에서 내려가며 태웠다. 이 경우 정렬을 제외하고 O(n^2)가 걸린다.
  • 하지만, 문제에서 2명으로 제한하고 있기 때문에 중요한건 최적으로 태우는 것이 아니었다.
  • 가장 무거운 사람을 태울 때, 가장 가벼운 사람하고만 비교하기만 하면 된다는게 핵심이었다.
• 처음부터 탐욕적으로 접근해야한다 파악했는데, 그 방향성이 잘못되서 틀리게 된게 아쉽다.