[프로그래머스] 구명보트 (탐욕 알고리즘)

탐욕 알고리즘을 적용하여 풀 수 있는 문제입니다.

 

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

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

 

탐욕 알고리즘에 대한 자세한 내용은 아래의 블로그에서 확인하실 수 있습니다.

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

 

탐욕 알고리즘에 핵심은 현재 상황에서 가장 최선의 선택을 하는 것인데

일반적으로 for loop를 한번 돌 때 마다 결과를 하나씩 찾아 나갈 수 있도록 문제를 해결해야 하는 것입니다.

 

이번 문제는 모든 사람을 구출하기 위한 구명보트의 최솟값을 구하는 문제입니다.

단 한개의 구명보트에 탈 수 있는 사람의 수는 2명이라는 점과, 구명보트가 견딜 수 있는 사람의 무게가 정해져 있다는 것입니다.

 

문제를 풀기위해 사람의 몸무게를 기준으로 sort를 하였습니다.

 

몸무게가 가장 가벼운 사람과 가장 무거운 사람을 한명씩 데리고 나와 구명보트에 탈 수 있는 무게인지 확인합니다.

무거워서 두명이 같이 탈 수 없다면 그것은 무거운 사람의 문제입니다.

가벼운 사람은 대기 무거운 사람은 구명보트에 태워서 보내버립니다.

다음 무거운 사람을 데리고 나와 가벼운 사람과 비교하고 둘이 같이 탈 수 있는 무게이면 같이 태워서 보내버립니다.

-- 반복 --

 

코드로 아래와 같이 구현을 하였습니다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {

        Arrays.sort(people);
        int frontIndex = 0;
        int endIndex = people.length - 1;
        int answer = 0;
        while (true) {
            if (frontIndex > endIndex) {
                break;
            }

            if (frontIndex == endIndex) {
                answer ++;
                break;
            }

            answer ++;
            if (people[frontIndex] + people[endIndex] > limit) {
                endIndex --;
                continue;
            }

            frontIndex ++;
            endIndex --;
        }
        return answer;
    }
}

 

위와 같이 복잡했던 코드를 아래와 같이 더 간결하게 작성을 할 수 있습니다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        int i = 0, j = people.length - 1;
        for (; i < j; --j) {
            if (people[i] + people[j] <= limit)
                ++i;
        }
        return people.length - i;
    }
}