문제

링크

풀이

1. people 배열을 정렬한다.

2. 맨 왼쪽값(최솟값)과 맨 오른쪽값(최댓값)을 더하여 limit 값과 비교한다.

   • 2개를 더한값 < limit 일 경우, 최댓값의 index-1 수행. (혼자 타는 경우)
   • 2개를 더한값 >= limit 일 경우, 최솟값의 index+1 하고 최댓값의 index-1 수행. (둘이 타는 경우)

3. 위 과정을 반복한다.

위 문제의 for문을 구현하는데 어려움을 많이 느꼈다... 위 문제의 for문을 구현할 때 주의할 점을 예시를 통해 설명해보려 한다.

people = {1,2,8,9,10,11}, limit = 10 이라 가정하자.

문제의 풀이를 따라하면 처음 1+11을 수행하게 된다. 하지만 10 (limit)을 초과한다. 이 말의 의미는 최댓값인 11은 people 배열의 어떠한 모든 값들과 더해져도 limit를 초과하게 된다. (people 배열은 정렬되어 있기 때문에 이 사실이 증명된다.) 따라서 무조건 보트를 혼자 타야한다. --> 따라서 limit를 초과하게 되면 다음 탐색에 최솟값은 고정시키고 최댓값의 index만 -1을 수행 후 탐색을 해야 구명보트의 최솟값을 구할 수 있게된다!

이후 1+10도 10 (limit)를 초과한다. 다음 탐색은 1+9인데 10 (limit) 이하이다. --> 2개를 더한값이 limit 이하이면 다음 탐색에 최솟값의 index+1, 최댓값의 index-1을 수행하면 된다!

이러한 방식의 for문을 구현해야 한다!

코드

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;


        // right(최댓값 index)만 for문 돌 때마다 하나씩 감소하게 됨. (left는 증감 X)
        // 2개 더한값이 limit 초과하면 left는 고정! (어차피 right는 감소됨.)
        // 2개 더한값이 limit 이하이면 left+1 수행! (어차피 right는 감소됨.)
        
        for (int i = right; i >= left; i--) {
            // 구명보트 혼자 타는 경우
            if (people[i] + people[left] > limit) {
                answer++;
            } 
            // 무게제한 맞아서 구명보트 딱 2명이서 같이 타는 경우
            else {
                answer++;
                left++;
            }
        }

        return answer;
    }
}