프로그래머스[Java] - 구명보트(그리디)

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

코딩테스트 연습 - 구명보트 | 프로그래머스

코드

import java.util.Arrays;
class Solution {
	public int solution(int[] people, int limit) {
		int answer = 0;
		int i = 0;
        int j;

		Arrays.sort(people);

		// 몸무게가 가장 무거운 사람부터 판단한다.
		for(j=people.length-1; i<=j; j--) {
			// 최소 + 최대 몸무게 2명의 합이 무게제한보다 큰 경우
			// 가장 큰 몸무게의 인원을 보트1대에 태워 보낸다.
			if(people[j] + people[i] > limit)
				answer ++;

			/* 최소 + 최대 몸무게 2명의 합이 무제게한보다 같거나 작은 경우
			 *  - 두명을 한 보트에 태워 보낸다.
			 *  - 그 다음으로 몸무게가 작은 인원을 기준으로 삼아야 하기 때문에 i값을 ++해준다.
			 */
			else {
				answer ++;
				i ++;
			}
		}

		return answer;
	}

}

풀이

논리를 생각해내는게 어려운 문제였다 ..

문제의 조건은 다음과 같다.

 

1. 구명보트는 최대 2명씩 밖에 탈 수 없다.

2. 구명보트에 태울 수 있는 무게 제한이 있다.

  - 사람들의 몸무게가 50kg, 60kg 이고 구명보트의 무게제한이 100kg이면 구명보트는 2개가 필요하다.

3. 구명보트를 최대한 적게 사용해 모든 사람을 구출한다.

 

가장 몸무게가 적은 인원과 가장 몸무게가 높은 인원의 합이 무게제한보다 크냐 작냐를 판단해서 해결하면 된다.

 

즉, 배열을 정렬해서 가장 오른쪽 원소와 가장 왼쪽 원소의 합을 구해서, 무게제한보다 크냐 작냐를 나누어 해결한다.

 

만약 가장 오른쪽 원소와 가장 왼쪽 원소의 합이 무게제한보다 크다면,

두 명은 함께 태울 수 없으므로 각각 따로 보트에 태워서 보낸다.

 

위와 반대로 두 원소의 합이 무게제한보다 작다면,

두 명은 함께 태울 수 있으므로 함께 보트에 태워서 보낸다.

그 후 가장 앞 원소는 보트에 태워 보냈으므로, 인덱스값을 +1해준다. (i++)

 

for문의 조건은 i<=j 인데, j값은 작아지고, i값은 커지므로 두 변수가 만날 때 까지 반복해서 보트를 태워서 보내면 된다.

보낼 인원이 홀수일 경우 => 두 값이 같아 지는 경우는 무조건 태워 보내야하므로 i=j도 조건에 포함한다.

 

ex) 몸무게 [20, 30, 30, 50, 60, 70, 80, 90, 100] 일때...

100kg, 90kg는 각각 따로 태워서 보낸다.

그 후 (80kg 20kg) , (70kg 30kg), (60kg 30kg) 을 보낸 후 50kg만 남으므로 1대를 더 보낸다.

(이때 i, j의 값은 둘다 3이다.)