Programmers - 구명보트

프로그래머스 구명보트 문제, 탐욕법(Greedy)에 관한 문제이다.

처음에는 모든 조합을 통해서 최소값을 구하려고 했는데,

RangeError: Maximum call stack size exceeded

위와 같은 오류가 자주 발생했다. 재귀함수를 잘못 구현했었는데, 다른 방법을 찾기로 했다.

---

풀이방법

sort()를 통해서 먼저 오름차순으로 나열을 해보면 시간소모를 덜 할 수 있을 것이라고 생각했다. 예를 들어서 [40, 70, 60, 80, 50]이 주어졌을 때, [40, 50, 60, 70, 80] 으로 재정렬해서 가장 가벼운 것과 가장 무거운 것을 매칭을 해서 하나씩 태워 보내는 방법을 생각했다.

function solution(people, limit) {
    let answer = 0;

    people = people.sort((a, b) => a - b);

    let start = 0, end = people.length - 1;

    while (start <= end) {
        if (people[start] + people[end] <= limit) {
            start++;
        }
        end--;
        answer++;
    }

    return answer;
}

진행상황

다음 그림은 입력된 배열 [40, 70, 60, 80, 50]과 구명보트 제한 무게 110으로 코드가 작동하는 모습을 그림으로 그려보았다.

• 흰색 : 현재 start와 end의 위치
• 파랑 : start++
• 주황 : end--

1. start 무게와 end 무게를 더해서 limit보다 작거나 같을 경우에는 보트에 태우지만, 그렇지 않을 경우 end만 보트에 태워서 보내게 된다. end--
2. 만약 limit보다 작거나 같을 경우에는 start와 end를 모두 보트에 태우므로, start++, end--를 해준다.
3. 1번과 2번 모두 보트를 사용하게 되므로 answer++를 해준다.
4. start와end가 엇갈리게 되면 반복문을 종료한다.

hanturtle님의 velog를 참고하였습니다 :)