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

문제 링크

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

프로그래머스

 

접근 방식

이 문제는 짝짓기 문제 유형이라고 생각합니다.

정렬을 해서 순차적으로 몸무게가 가벼운 사람들끼리 짝을 짓게 되면 틀리는 문제입니다.

반례는 다음과 같습니다. (단, 보트가 실을 수 있는 최대 무게는 100 입니다.)

people : [30,30,70,70,40]
answer : 3

 

제일 몸무게가 적게 나가는 사람들끼리 묶어주는 방식으로 풀게 되면 아래와 같이 됩니다.

(30,30), (40), (70), (70)

 

보트가 4개가 필요하게 됩니다. 하지만 최소의 보트 갯수는 3개 이므로, 정답이 아닙니다.

 

선택한 두 사람의 무게의 합이 보트가 실을 수 있는 최대 무게에 근접하도록 짝지어야 합니다.

(30,70), (30,70), (40)

 

이렇게 짝을 지어주면 3개의 보트로 모든 사람을 나를 수 있습니다.

 

어떤 알고리즘을 사용할까요?

 

Two-Pointer 알고리즘을 사용합니다.

 

왜 Two-Pointer 알고리즘을 사용할까요?

 

투 포인터는 두 개의 포인터를 사용하여 데이터를 탐색하거나 특정 조건을 만족하는 값을 찾는 알고리즘입니다.

 

Two-Pointer 알고리즘을 사용하는 이유는 정렬O(NlogN)된 배열에서 특정 조건을 만족하는 두 요소를 빠르게 찾을 수 있기 때문입니다.

또한, 완전 탐색 방식으로 모든 사람의 조합을 고려하면 시간 복잡도가 O(N²) 이지만, Two-Pointer를 사용하면 O(N)으로 줄일 수 있습니다.

 

왜 사람 무게순으로 정렬을 해주어야 할까요?

 

정렬 후 투 포인터를 사용하면 최대 무게 제한을 초과하지 않는 가장 최적의 조합을 빠르게 찾을 수 있습니다.

투 포인터 알고리즘을 사용하기 위해서는 배열이 정렬되어 있어야 합니다. 왜냐하면 정렬을 하면 맨 왼쪽(첫 번째 요소)은 가장 가벼운 사람, 맨 오른쪽(마지막 요소)은 가장 무거운 사람이라는 전제가 성립하기 때문입니다.

 

이 문제에서 보트의 개수를 최소화하려면 가장 무거운 사람부터 처리하는 것이 핵심입니다.
즉, 가장 무거운 사람을 혼자 태울지, 아니면 가장 가벼운 사람과 함께 태울지를 빠르게 결정해야 합니다.
이를 위해 배열을 정렬하면 가장 무거운 사람이 항상 맨 끝에 존재"하는 구조를 만들 수 있습니다.

 

풀이 코드

import java.util.*;

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

 

시간 복잡도

배열 정렬 + 투 포인터 방식으로 시간복잡도는 O(NlogN + N)이 걸립니다.

 

출력 결과