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

문제

---

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

프로그래머스

 

문제 분석

---

[제한사항]

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

 

무인도에 갇혀있는 사람들을 구하기 위해 2인용 구명보트를 최소한으로 사용하여 사람들을 구출하는 방법을 구하는 문제이다.

구명보트에는 무게 제한이 있어 두 사람의 무게의 합이 무게 제한보다 작아야 한다.

 

가장 효율적으로 보트에 태우는 방법은 아마 제일 무게가 많은 사람과 적은 사람을 태우는 방법일 것이다. 

그래야 가장 적게 보트가 이동한다.

 

무게가 제일 많이 나가는 사람과 제일 적게 나가는 사람의 합이 무게 제한을 넘어가면 무게가 제일 많이 나가는 사람 한명만 보트를 타고 나간다. 

그렇지 않으면 둘이 같이 타고 나간다.

 

문제 접근

---

처음에는 리스트를 만들고 정렬 후 제일 무거운 사람과 제일 가벼운 사람의 합이 무게 제한을 넘지 않는다면 함께 리스트에서 빼주고, 넘는다면 무거운 사람만 리스트에서 빼주면 서 문제를 풀었다.

 

하지만 효율성 테스트에서 시간 초과가 있어 코드를 좀 더 효율적으로 최적화할 필요가 있었다.

 

아마 리스트 넣고 빼고 하는 과정이 문제가 된 것으로 보인다.

(리스트를 만드는데) 5*10^4 + (리스트에서 빼는데)  5*10^4 = 10^9 으로 시간 초과가 난다.

 

그래서 투포인터를 활용하여 문제를 해결했다.

 

우선 배열을 정렬한 후 가장 끝에는 무게가 제일 큰 사람의 인덱스, 가장 앞에는 무게가 제일 작은 사람의 인덱스로 사용하였다.

 

두 인덱스가 서로 만나 위치가 뒤 바뀔 때 까지

무게가 큰 사람이 나가면 무게가 큰 사람의 인덱스를 1 빼주고,

무게가 작은 사람이 나가면 무게가 작은 사람의 인덱스를 1 더해주었다.

 

코드

---

import java.util.*;

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