[99클럽 코테 스터디 19일차 TIL] 프로그래머스 - 구명보트

99클럽 코테 스터디 19일차 TIL 입니다.

[level 2] 구명보트 - 42885

문제 링크

구분

탐욕법（Greedy）

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.

• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.

• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.

• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

people	limit	return
[70, 50, 80, 50]	100	3
[70, 80, 50]	100	3

---

풀이 코드

import java.util.Arrays;

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

• Time: 12.63 ms

• Memory: 56.8 MB

해당 문제는 투포인터 알고리즘으로 쉽게 풀 수 있는 문제였다. 보트를 가장 적게 사용하기 위해서는 최대한 2명씩 태우고 옮기는게 좋고 이때 옮기는 2명의 몸무게가 클수록 좋다. 왜냐하면 몸무게가 낮은 사람을 2명씩 먼저 옮겨버리면 몸무게가 낮은 사람이랑은 같이 보트로 이동할 수 있는 무거운 사람들을 한명씩만 옮겨야하기 때문이다. 예를 들면 아래의 경우가 있다.

• 사람의 몸무게 배열 : [50, 50, 60, 70]

• 보트에 탈 수 있는 몸무게 제한 : 120kg

위 경우에서 보트를 가장 적게 이동하는 횟수는 [50, 70], [50, 60] 으로 2 이다. 하지만 만약 몸무게 낮은 사람부터 옮기게 되면 [50, 50] 옮기고 [60, 70] 은 무게 제한 120kg 보다 크기 때문에 한명씩 옮겨야 한다.

따라서 몸무게가 무거운 사람을 낮은 사람과 최대한 매칭해서 옮기는게 보트를 가장 적게 사용할 수 있다. 이를 구현하기 위해 먼저 몸무게 배열을 오름차순으로 정렬하고 몸무게가 가장 낮은 사람의 인덱스 변수 start 와 몸무게가 가장 무거운 사람의 인덱스 변수 end 을 선언해 무게 제한과 크기 비교를 통해 이동 횟수를 증분했다.

• start + end <= limit : 몸무게가 가장 낮은 사람과 무거운 사람을 보트로 옮긴다.

  • 보트 이동 횟수 + 1

  • start++ : 그 다음 몸무게 낮은 사람

  • end-- : 그 다음 몸무게 무거운 사람

• start + end > limit : 몸무게가 무거운 사람은 몸무게가 가장 낮은 사람과도 보트를 탈 수 없으므로 어차피 혼자 보트를 타야한다.

  • end-- 그 다음 몸무게 무거운 사람

그리고 가장 마지막에 혼자 남게 되는 경우, while 문이 끝나버린다. 이 경우를 확인해서 이동 횟수를 추가하기 위해 if (start == end) 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;
    }
}

• Time: 10.66 ms

• Memory: 56.4 MB

다른 사람의 풀이인데 성능적으로 훨씬 빠르다. 풀이 과정은 비슷하지만 마지막에 구명보트의 이동 횟수를 구하는 부분이 정말 신기했다. people.length 에서 i 값을 빼주고 있는데 이 연산이 왜 구명보트의 최소 이동 횟수가 되는지 이해하느라 한참 머리를 썼다. 그 이유는 아래와 같다.

1. 사람 수 = 무게 제한 초과 사람들 + 짝지어 탄 사람 + 짝지어 탄 사람

2. 사람 수 = 1명 태운 보트 수 + 2명 태운 보트 수 + 2명 태운 보트 수

3. 사람 수 - 짝지어 탄 사람 = 무게 제한 초과 사람들 + 짝지어 탄 사람

4. 사람 수 - 2명 태운 보트 수 = 1명 태운 보트 수 + 2명 태운 보트 수

이해가 될지 모르겠다. 보트의 이동 횟수는 결국 1명 태운 보트 횟수와 2명 태운 보트 횟수의 합이다. 위 연산 과정에 따라 사람 수에서 2명 태운 보트 수를 빼면 보트의 이동 횟수가 나온다. 어떻게 이런 생각을 하는지 참 신기하다.

---

돌아보기

뭔가 풀이법이 바로 생각나고 그대로 풀어지고 또 해당 방법이 상당히 괜찮은 방법이었을 때 너무 재밌는 것 같다.

다음에는

• 오늘처럼 하기

---

#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL