[ 알고리즘 ] 코딩 - Programmers - 구명보트.Java

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

코딩테스트 연습 - 구명보트

* Programmers - Level 2 - 구명보트.java

* 최대 2명의 사람만 탈 수 있음

입출력 예시

---

* 아래와 같은 로직!

* 우선 people을 정렬한다.

* 정렬된 배열을 가지고 가장 가벼운 사람이 있는 index와 가장 무거운 사람이 있는 index를 가지고

* 탐욕(Greedy)알고리즘을 이용해서 해결했다.

* 가장 무거운 사람이 다른 사람과 탈 수 없으면 boatCnt++하고 maxIndex-1

* 가장 무거운 사람과 다른 사람과 탈 수 있으면 boatCnt++하고 maxIndex-1, minIndex+1

* minIndex와 maxIndex가 교차하는 순간 루프 정지

로직 예시

---

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
		Arrays.sort(people);
		
		int maxWeight = people.length-1; // 가장 무거운 사람
		int boatCnt = 0; // answer
		int minWeight = 0; // 가장 가벼운 사람
		
		while(maxWeight >= minWeight) { // Index가 교차하지 않을 때 까지
			int sum = people[maxWeight] + people[minWeight];
			if(sum <= limit) { // 제한보다 작으면
				maxWeight--; // 가장 무거운사람 보내고
				minWeight++; // 가장 가벼운사람도 보내고
				boatCnt++; // 보트추가
			} else { // 제한보다 크면 
                     // --> 가장 무거운사람과 가장 가벼운사람의 합이 제한보다 크므로
                     // 무조건 혼자 가야한다.
				boatCnt++; // 보트추가
				maxWeight--; // 가장 무거운사람만 보낸다
			}
		}
		
        return boatCnt;
    }
}

 

* 탐욕기법이 그렇 듯 코드 자체는 간결하다!