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

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42885

프로그래머스

 

🔍  해결 과정

무인도에 갇힌 사람은 최대 5만명이기 때문에 제한된 무게 안에서 일반적인 방식으로 두 사람을 일일이 선택해서 나올 수 있는 사용가능한 보트의 수 중 최솟값을 도출하기에는 시간초과의 우려가 있습니다. 이중 반복문을 통해서 선택하려고만 해도 연산량이 1억을 초과하기 때문입니다.

 

그래서 또 다른 해결 방법은 투 포인터의 방식을 사용해 사용가능한 보트의 최솟값을 바로 도출해내는 방법이 있습니다.

투 포인터를 쓴 이유의 핵심은 제한된 무게에 최대한 가깝도록 두 명을 선택해야 최소의 보트값을 도출할 수 있기 때문입니다. 그래서 우선 주어진 사람들을 무게 순으로 오름차순으로 정렬한 다음 양쪽 끝을 집어서 무게를 비교하여 보트의 개수를 카운트하는 과정을 생각했습니다.

 

예를 들어 제한된 몸무게는 110이고, 다음과 같은 몸무게를 가진 사람들이 존재한다고 가정해봅시다. 주어진 몸무게를 오름차순으로 미리 정렬하여 나열하겠습니다.

제한된 몸무게: 110
몸무게: [50, 50, 55, 60, 61]

 

여기서 최소 보트값을 도출하는 과정은 다음과 같습니다.

1. 왼쪽 구역을 가리키는 인덱스 leftIdx를 지정한다. (초기값은 인덱스 0인 50을 가리키고 있다.)
2. 오른쪽 구역을 가리키는 인덱스 rightIdx를 지정한다. (초기값은 인덱스 마지막 부분인 61을 가리키고 있다.)
3. 1번과 2번이 가리키고 있는 몸무게의 합을 도출하여 제한된 몸무게와 비교한다.
    3-1. 만약 제한된 몸무게를 초과한다면 rightIdx가 가리키는 곳을 왼쪽으로 한 칸 앞당기고 보트 수를 하나 카운트한다.
    3-2. 제한된 몸무게 이하라면 leftIdx를 오른쪽으로 한 칸 이동해준다. 마찬가지고 rightIdx도 왼쪽으로 한 칸 이동해준 다음 보트 수를 하나 카운트한다.
4. 1번 부터 3번의 과정을 반복하여 leftIdx와 rightIdx가 서로 역전될 때가지 진행한다.

 

이러한 방식으로 진행한다면 시간복잡도는 O(N) (N: 사람 수)만큼의 연산 만에 답을 도출할 수가 있습니다.

---

✏️ 코드

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;
            }
            
            --right;
            ++answer;
        }
        
        return answer;
    }
}