문제 출처

코딩테스트 연습 > 탐욕법(Greedy) > 구명보트
https://school.programmers.co.kr/learn/courses/30/lessons/42885

문제 설명

사람들 몸무게가 담긴 배열 people, 무게 제한 limit이 주어질 때, 모든 사람을 구출하기 위한 최소한의 구명보트 개수 return하라.

접근 방법

몸무게 배열 people 정렬하고, 가장 가벼운 사람 index light, 가장 무거운 사람 index heavy를 지정한다.

이 후, 가장 무거운 사람과 가벼운 사람의 무게를 더했을 때 limit를 넘지 않으면 그 가벼운 사람의 다음 사람을 확인(light++)한다.
태웠다는 가정하에 heavy--; 하여 그 다음으로 덜 무거운 사람을 확인한다.

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        
        int light = 0;
        int heavy = people.length -1;
        
        while(light <=heavy){
            if(people[light] + people[heavy] <= limit){
                light++;
            }
            heavy--;
            answer++;
        }
        return answer;
	}
}

Reiview

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int light = 0;
        int heavy = people.length-1;
        
        Arrays.sort(people);
        
        while(light <= heavy){
            if(people[light] + people[heavy] <= limit){
                light++;
            }
            heavy--;
            answer++;
        }
        return answer;
    }
}

알게된 점

처음 문제를 풀 땐, 정렬까진 고려했었는데 가벼운 사람들부터 뒤로 진행하면서 보트 무게가 limit될 때까지 더하는 방식을 진행했다. 하지만 해당 방식은 그리디로 푸는 것에는 약간 어긋난 방식이었다.
"가장 무거운" 사람을 "가장 가벼운" 사람과 같이 태우는 방식이 이 문제의 keypoint 였다.

% 이 문제를 3사람 이상까지 고려했었는데, 문제에는 최대 2사람까지 탈 수 있다고 적혀있었다. 문제를 똑바로 읽자

문제푼 흔적

Review