99클럽 코테 스터디 15일차 TIL, 탐욕법(구명보트)

1. 문제 정의

2. 문제 접근

탐욕법에 속해 있으니 greedy방식으로 풀면 될 것 같다.

3. 문제 풀이

1. 배열을 정렬해준다.
2.  2개의 포인트를 두어 차례대로 탐색한다.
3.  정답을 갱신한다.

4. 코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
       int answer = 0;
        // 정렬해줘서 해야 최소 몸무게와 최대 몸무게의 사람을 선정해서 이용 가능
        Arrays.sort(people);
        int l = people.length;
        // 투포인터 이용
        int p1 = 0;
        int p2 = l -1;
        // 그때마다 최선의 방식을 선택
        while(p1 <= p2){
            if(people[p1]+people[p2] <= limit){
                answer++;
                p1++;
                p2--;
            } else {
                answer++;
                p2--;
            }
        }
        return answer;
    }
}

5. 회고

최대 2명까지 보트에 탈 수 있다는 것에서 투포인터가 생각이 났고, 투포인터로 하니 문제가 쉽게 해결되었다.