[프로그래머스, 42885] 구명보트 (java)

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

프로그래머스

728x90

---

메모리: 54.1 MB, 시간: 11.27 ms

사용 알고리즘: 투 포인터

 

일단 사람들의 몸무게를 오름차순으로 정렬한다.

그리고 투 포인터를 사용할 건데,

하나의 포인터는 현재 가장 가벼운 사람, 다른 하나의 포인터는 현재 가장 무거운 사람을 가리킨다.

현재 가장 무거운 사람을 구명보트에 태우고 가장 가벼운 사람이 이 구명보트에 탈 수 있는지 확인한다.

탈 수 있다면 함께 태워 보내고 탈 수 없다면 가장 무거운 사람만 태워 보낸다.

이 과정을 모든 사람들이 탈 때까지 반복한다.

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        
        // 몸무게 오름차순 정렬
        Arrays.sort(people);
        
        // 가벼운 사람 먼저 가리키는 포인터
        int l = 0;
        // 무거운 사람 먼저 가리키는 포인터
        int r = people.length - 1;
        
        int answer = 0;
        while(l <= r) {
            // 현재 가장 무거운 사람과 현재 가장 가벼운 사람이 함께 이동할 수 있는지 체크
            
            if(people[l] + people[r] <= limit) { // 함께 이동할 수 있는 경우
                answer++;
                l++; // 둘 다 이동
                r--;
            }
            else { // 함께 이동할 수 없는 경우
                answer++;
                r--; // 무거운 사람만 이동
            }
        }

        return answer;
    }
}