[프로그래머스] 구명 보트 (Lv2)

문제

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

---

고민1. 구명보트를 최소로 사용하려면?

최대한 두 명씩 태우기 위해서는 limit를 넘지 않는 선에서
가장 무거운 사람은 가장 가벼운 사람과 보트를 타도록 하는것이 좋다.
예를 들어, limit=100이고 40 50 50 60 일 경우 (40,50) (50) (60) 보다
최솟값과 최댓값을 짝지은 (40,60) (50,50)이 횟수가 적다

고민2. 최댓값과 최솟값 짝짓기

포인터 두 개를 사용하여 앞, 뒤를 접근하고
맨 앞과 맨 뒤의 합이 limit를 넘지 않으면 앞,뒤 포인터를 이동시키고
limit를 넘는다면 뒤 포인터만 이동시킨다.
(Deque와 같은 원리)

구현 시 주의할 점은
1. f(앞 포인터)가 l(뒤 포인터)보다 뒤에 있다면 배열을 모두 순회했다는 의미이다.
2. f==l이라면 한 명만 남았다는 의미이다.

이를 고려하여 while문을 작성하였다.

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int f=0;
        int l=people.length-1;  
        
        Arrays.sort(people);
        
        while(f<=l){
            if(f==l){   // 한 명만 남은 경우
                ++answer;  
                break;
            }
            else{
                int total=people[f]+people[l];
                if(total<=limit){
                    ++f;
                    --l;
                    ++answer;              
                }
                else{
                    --l;
                    ++answer;
                }
            } 
        };
        return answer;
    }
}

---

최종코드

GitHub Java-algorithm-practice/프로그래머스/lv2/42885. 구명보트/

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int f=0;
        int l=people.length-1;  
        
        Arrays.sort(people);
        
        while(f<=l){
            if(f==l){   // 한 명만 남은 경우
                ++answer;  
                break;
            }
            else{
                int total=people[f]+people[l];
                if(total<=limit){
                    ++f;
                    --l;
                    ++answer;              
                }
                else{
                    --l;
                    ++answer;
                }
            } 
        };
        return answer;
    }
}