[프로그래머스] 구명보트 - 탐욕법(Greedy)

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

프로그래머스

 

위 문제는 탐욕법으로 해결하였다.

 

2022.09.20 - [알고리즘] - [알고리즘] 탐욕 알고리즘(Greedy Algorithm)

[알고리즘] 탐욕 알고리즘(Greedy Algorithm)

 

문제

 

풀이 방법

1. 배열 people을 오름차순으로 정렬한다.
2. 정렬한 people의 최소 몸무게와 최대 몸무게의 합을 구하고 limit이 넘지 않을 경우 둘을 보트에 태워보낸다.
   (min 인덱스 +1, max 인덱스 -1, .answer +1)
3. 정렬한 people의 최소 몸무게와 최대 몸무게의 합이 limit을 넘을 경우 최대 몸무게인 사람만 보트에 태워보낸다.
   (max 인덱스 -1, answer +1)
4. min 인덱스가 max 인덱스와 같아지면 남은 한명을 태워보내고 반복문을 종료한다.
   (answer +1)
5. min 인덱스가 max 인덱스보다 커지면 모두 태워보낸것이므로 반복문을 종료한다.

 

디버깅 

• 입력

people	limit
[70, 50, 80, 50]	100

 

• 결과

3

 

• 디버깅

people	limit	min	max	answer (보트 수)
[70, 50, 80, 50]	100
[50, 50, 70, 80]	100	0	3	0
[50, 50, 70, 80]	100	0	2	1
[50, 50, 70, 80]	100	0	1	2
[50, 50, 70, 80]	100	1	0	2

 

소스 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        
        int answer = 0;

        Arrays.sort(people); // 오름차순 정렬
        
        int min = 0;
        int peopleLen = people.length;
        
        for (int max = peopleLen - 1; min <= max; max--) {
        
        	// 두 사람의 몸무게 합이 limit 이하일 경우 min에 해당하는 사람도 보트에 태워보낸다.
            if (people[min] + people[max] <= limit) {
                min++;
            }
            
            // max에 해당하는 사람도 보트에 태워보내고, 사용한 보트의 수를 증가시킨다.
            answer++;
        }
        
        return answer;
    }
}