프로그래머스 LV.2 구명보트

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

프로그래머스

 

문제 설명 :

 

무인도에 갖힌 사람들을 구해야한다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다.

[70, 50, 80, 50] 을 예를 들면 2번째 4번째 사람과 같이 탈 수 있지만, 1번째 3번째 사람은 limit가 초과해서 안된다.

문제 출력 조건은 구명보트를 최대한 적게 사용하여 모든 사람을 구출 해야한다.

 

문제 해설 :

 

최대 2명씩 이라는 조건을 보았을때 투 포인터 알고리즘을 떠올렸으면 성공이다.

배열을 Arrays.sort() 메소드를 호출하여 정렬을 해준다.

제일 왼쪽 인덱스를 left, 제일 오른쪽 인덱스를 right로 설정하고 두 포인터가 역전될떄까지 비교한다.

right가 감소하는 조건은 따로 없고 left와 right 포인터가 역전되기 전까지는 증가시킨다. 왜냐하면 무게가 큰 포인터를 가르키고 있기 때문

left가 증가하는 조건은 right 포인터와 무게를 합쳤을때 limit 보다 작거나 같으면 증가시킨다.

역전이 발생했을때 while() 루프를 종료시키고 값을 리턴한다.

 

소스코드 :

import java.util.*;
import java.io.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0, left = 0, right = people.length-1;
        Arrays.sort(people);
        while(left<=right) {
        	if(people[left]+people[right]<=limit) {
            	left++;
            }
            right--;
            answer++;
        }
        return answer;
    }
}