Today I Learned

오늘은 어제 공부했던 내용을 문제로 풀어보려했다.

구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

• 문제
  사람들의 몸무게가 배열로 주어지고 구명보트가 태울 수 있는 최대 몸무게가 주어진다. 한 보트에 사람은 최대 2사람이 탈 수 있을 때, 모든 사람을 구하기 위해 필요한 가장 최소한의 구명보트 수를 구해라.

• 풀이 과정

1. 주어진 배열에서 부분의 합을 구하는 문제이므로 간단하게 투포인터 방식을 사용하면 풀릴 것이라 생각했다.

2. 투포인터를 적용하기 위해 우선 주어진 배열을 sort 한다.

3. left와 right 변수를 배열의 양 끝 인덱스를 가르키게 해서 시작한다.

4. left의 몸무게와 right의 몸무게가 합쳐서 리미트를 넘지 않으면 left와 right를 한칸씩 당기면서(left++ && right--) 배의 카운트를 하나 늘린다.

5. 만약 리미트를 넘어가면 무거운 사람(right)혼자 타야하므로 left는 줄이지 않고 right만 줄이면서(right--) 카운트를 늘린다.

6. 총 카운트를 반환하면 끝.

• 구현 코드

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