프로그래머스 구명보트 자바 풀이

문제 링크

문제 요약

구명보트는 한 번에 최대 2명, 무게 제한 limit이 있다
모든 사람을 구출하는 데 필요한 구명보트 개수의 최솟값을 구한다
무게 제한은 항상 사람들 몸무게의 최댓값보다 크게 주어진다

문제 풀이

처음에는 가장 무거운 사람부터 순서대로 보면서, 그 사람과 함께 탈 수 있는 사람을 나머지 중에서 찾아 짝짓는 방식을 생각했다.

하지만 이 방식은 비효율적이다.

사람 수가 최대 50,000명인데, 짝을 지을 때마다 나머지 사람을 전부 훑으면 O(n^2)이 되어 시간 안에 끝나지 않는다.

이 문제의 핵심은 가장 무거운 사람은 무조건 보트 한 자리를 쓰고, 남은 자리에 가장 가벼운 사람을 태울 수 있는지만 확인하면 된다는 점이다.

몸무게를 정렬한 뒤 양 끝에서 포인터 두 개로 접근한다.

가장 무거운 사람과 가장 가벼운 사람의 무게 합이 limit 이하면 둘을 같이 태운다
넘으면 가장 무거운 사람 혼자 태운다
어느 쪽이든 보트는 한 척 필요하므로 그때마다 개수를 하나 늘린다

최종 코드

java

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people); // 몸무게 오름차순 정렬
        int left = 0; // 가장 가벼운 사람
        int right = people.length-1; // 가장 무거운 사람
        
        
        while(left<= right){ // 두 포인터가 교차할 때까지 반복
            if(people[left] + people[right--] <= limit){ // 가장 가벼운 사람과 무거운 사람을 같이 태울 수 있으면
                left++;
            }
            answer++; // 보트 한 척 사용
        }
        
        return answer;
    }
}

구명보트

문제 요약

문제 풀이

최종 코드

함께 읽으면 좋은 글

택배상자

롤케이크 자르기

할인 행사

숫자 변환하기