[프로그래머스] 탐욕법 : 구명보트

       문제 요약        

- 문제

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

         아이디어        

제일 몸무게가 가벼운 사람 + 무거운 사람을 같이 태울 수 있는 지 확인해야 함

만약에 못태워? -> 무거운 사람을 위한 보트 하나 내주기

 

+설명 추가)

가장 무거운 사람을 기준으로 가능한 최선의 조합을 찾기

그리디 알고리즘의 핵심은 최대한 무거운 사람과 가벼운 사람을 짝지어 보트 개수를 줄이는 것

 

         소스코드        

 

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);
        // 최대 2명씩 밖에 탈 수 없음 -> 무거운 친구랑 가벼운 친구 같이 태우는 게 효율적
        int i = 0, j = people.length-1;
        while(i<j){
            if(people[i] + people[j]<=limit){
                i+=1;
                j-=1;
                answer+=1;
            }else {
                j-=1;
                answer+=1;
            }
        }
        if(i== j){
            answer +=1;
        }
        return answer;
    }
}

 

3명이면 어카냐?

-> 동일한 원리로 가장 무거운 애들 그룹화 가능한지 불가능하면 2명 .. 또 불가능하면 1명

import java.util.Arrays;

public class Solution {

	public static void main(String[] args) throws Exception {
		int[] people = new int[] { 70, 50, 80, 50 };
		int limit = 100;
		solution(people, limit);

	}

	static int solution(int[] people, int limit) {
		Arrays.sort(people);
		int left = 0, right = people.length - 1;
		int boats = 0;
		while (left <= right) {
			if (left < right - 1 && people[left] + people[right] + people[right - 1] <= limit) {
				left += 1;
				right -= 2;
			} else if (people[left] + people[right] <= limit) {
				left += 1;
				right -= 1;

			} else {
				right -= 1;
			}
			boats += 1;
		}

		return boats;
	}

}