[프로그래머스] Lv.1 구명보트 (Greedy 알고리즘, Java)

 

문제설명

입력 & 출력

나의 풀이

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int minWeight = 0; // 가벼운 사람을 가리킬 인덱스
        int maxWeight = people.length-1; //무거운 사람을 가리킬 인덱스
        int boat = 0; // 보트 수
        
        Arrays.sort(people); //오름차순 정렬
        
        while(minWeight <= maxWeight){ //두 인덱스가 교차할 때 까지 반복
            boat++; // 보트 개수 추가
            
            if(people[minWeight] + people[maxWeight] <= limit){
                minWeight++;
            }
            maxWeight--;
        }
        
        return boat;
    }
}

 

이번 문제는 무인도에 갇힌 사람들을 2명의 제한과 몸무게 제한도 있는 구명보트로 최대한 적게 구명보트를 사용하여 모든 사람을 구하는 문제입니다.

 

 그리디 알고리즘을 활용하기에 적합한 문제입니다. 왜냐하면 가장 무거운 사람과 가장 가벼운 사람을 태울 수 있는지 검사하고 이를 통해 보트의 수를  최소화 할 수 있기 때문입니다.

 

이는 국소 최적해의 선택에도 부합합니다. 따라서 그리디 알고리즘을 사용하기에 적합한 문제입니다.

 

---

먼저 가장 무거운 사람을 가리키는 인덱스 maxWeight와 가장 가벼운 사람을 가리키는 minWeigth를 지정해줍니다.

 

예제1번을 예로들자면 [70,50,80,50]을 Arrays.sort()메서드로 오름차순으로 정렬해줍니다. 그리고 가장 무거운사람을 가리키는 인덱스와 가장 가벼운 사람을 가리키는 인덱스를 0번과 배열의 끝으로 지정해줍니다.

 

그리고 반복문을 돌려주는 데 이 때 조건을 두 인덱스가 같아지거나 교차할때까지 반복을 해줍니다.

 

반복문 안에서는 people[minWeight] + people[maxWeight]가 limit를 넘지않으면 두명에서 같이 탈 수 있고, 넘으면 무거운 사람 혼자 가야됩니다.

 

이해가 쉽도록 그림으로 표현해보았습니다.

(1)

• 현재 배열 상태: [50, 50, 70, 80]
• minWeight: index 0 (50)
• maxWeight: index 3 (80)
• 두 사람의 합 (50 + 80) > 100(limit) 이므로, 가장 무거운 사람만 태웁니다.
• maxWeight를 감소시킵니다. 즉 다음 무거운 사람을 가리킨다: index 2
• 필요한 보트의 수: 1

 

(2)

마찬가지로 

• 현재 배열 상태: [50, 50, 70, 80]
• minWeight: index 0 (50)
• maxWeight: index 2 (70)
• 두 사람의 합 (50 + 70) > 100(limit) 이므로, 가장 무거운 사람만 태웁니다.
• maxWeight를 감소시킵니다. 즉 다음 무거운 사람을 가리킨다: index 2
• 필요한 보트의 수: 2

(3)

• 현재 배열 상태: [50, 50, 70, 80]
• minWeight: index 0 (50)
• maxWeight: index 1 (50)
• 두 사람의 합 (50 + 50) == 100(limit) 이므로, 두 사람을 함께 태웁니다.
• minWeight를 증가시킵니다. 즉 다음 가벼운 사람을 가리킨다. index 1
• maxWeight를 감소시킵니다. 즉 다음 무거운 사람을 가리킨다: index 1
• 필요한 보트의 수: 3
• 두 인덱스가 같아졌기 때문에 반복문 탈출

 

그러면 최종적으로 필요한 보트의 수는 3이됩니다.

 

 

참고❗️

[Algorithm] 그리디 알고리즘(탐욕법, greedy, Java) 알아보기