[PS] 99클럽 코테 스터디 19일차 TIL (구명보트)

문제

문제 링크

설명

구명보트의 무게 제한이 있고 최대 2명까지만 태울 수 있다. 배열의 사람을 모두 옮기는 데 필요한 구명 보트의 수를 리턴한다.

풀이

1. 먼저 입력받은 배열을 오름차순으로 정렬해 인덱스로 접근하기 편하도록 만든다.
2. 가장 가벼운 사람과 가장 무거운 사람을 태워보고, 무게 제한에 걸리지 않으면 answer 를 1 증가 시킨다.
3. 그리고 맨 처음 인덱스(가장 가벼운 사람의 인덱스)를 1 증가시키고 가장 오른쪽(가장 무거운 사람의 인덱스) 를 1 감소시켜 배열을 양쪽에서 탐색하도록 한다. (투 포인터)

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++;
      }
      answer++;
      right--;
    }
    return answer;
  }
}