[프로그래머스] 구명보트

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

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

 

문제는 위와 같으며 문제 조건 중 배에는 최대 2명만 탈 수 있다는 것을 기억해야 합니다. 따라서 무게가 많이 나가는 사람을 먼저 태운 뒤, 무게가 덜 나가는 사람을 같이 태울 수 있는지 없는지 판단하는 방식으로 문제를 해결하였습니다.

 

예를 들어 [70, 50, 80, 50, 20], limit = 100 이 주어진 경우

1. 사람들을 무게순으로 먼저 정렬합니다.

2. 이후 제일 무게가 많이 나가는 사람과 제일 무게가 적게 나가는 사람을 동시에 태우는 것이 가능하다면 둘을 태우고

3. 그렇지 않다면 무게가 많이 나가는 사람만 보트에 태우고 보트 수를 증가시킵니다. (2, 3 과정을 반복)

4. 최종적으로 젤 무게가 나가지 않는 사람까지 보트에 모두 오르면 반복을 종료하고 보트 수를 반환합니다.

 

 

코드는 다음과 같습니다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;

        // 무게순으로 정렬하기 (오름차순)
        Arrays.sort(people);

        int head = 0;                  // 처음 사람을 가리키는 인덱스
        int tail = people.length - 1;  // 마지막 사람을 가리키는 인덱스

        // 처음 사람과 마지막 사람이 같아질 때까지 반복
        while (head <= tail) {
            int first = people[head];
            int last = people[tail];

            // 처음 사람의 무게와 마지막 사람의 무게의 합이 제한보다 작거나 같은 경우
            if (first + last <= limit) {
                head++;  // 처음 사람도 배에 태울 수 있으므로 처음 사람 인덱스를 다음으로 이동
            }

            // 마지막 사람의 경우 처음 사람과의 무게의 합이 제한보다 큰지 작은지에 상관없이 항상 배에 먼저 태움
            // 따라서 마지막 사람 인덱스는 항상 하나 감소
            tail--;
            answer++;  // 처음 사람 + 마지막 사람 또는 마지막 사람만 태운채로 보트 수 증가
        }

        return answer;
    }
}