Programmers - 구명보트 with JAVA

 

 

 

문제의 조건은 아래와 같다

1. 구명보트에는 두명까지 탈 수 있다.

2. 두사람의 몸무게의 합이 limit보다 작아야 한다.

3. 최소한의 보트를 사용하여 모든 사람을 구조한다.

 

 

 

 

로직

1. 몸무게 배열을 정렬한다.

2. 투포인터를 활용해 보트의 태울 사람을 정한다.

 

• 왼쪽의 해당하는 무게와 오른쪽의 해당하는 무게의 합이 limit이하라면 둘 다 태우고 왼쪽, 오른쪽 인덱스 모두 변경
• 아니라면 무거운 쪽에 해당하는 오른쪽의 무게만 태우고 오른쪽 인덱스 변경
• 만약 오른쪽, 왼쪽 인덱스 값이 같아진다면 한명 태우고 종료

 

 

 

[50, 20, 30, 70, 30, 40] 이라는 데이터가 있고 limit이 100이라고 가정한다.

정렬하면 [20, 30, 30, 40, 50, 70, 90]이 된다.

이때 왼쪽 포인터 0, 오른쪽 포인터 5로 시작한다.

20 + 90 > 100 이므로 오른쪽 포인터만 감소시키고 보트의 수 증가시킨다. 즉, 90만 태워서 보낸다.

20 + 70 < 100 이므로 왼쪽 포인터는 1을 증가시키고 오른쪽 포인터는 1을 감소시킨다. 즉, 20과 70을 태워서 보낸다.

... 이런식으로 진행한다.

 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        int point1 = 0;
        int point2 = people.length-1;
        while(point1 <= point2){
            if(people[point1] + people[point2] > limit){
                point2 -= 1;
                answer += 1;
            }
            else{
                point1 += 1;
                point2 -= 1;
                answer += 1;
            }
        }
        return answer;
    }
}