프로그래머스 - 구명보트 (Java, 투포인터)

아이디어

투포인터

 

풀이

어차피 2명씩밖에 못 타니,

가장 무거운 사람과 가장 가벼운 사람을 함께 태울 수 있다면 함께 태워버리고

아니라면 무거운 사람만 태우도록 했다.

 

먼저 정렬을 한다.

가장 가벼운 사람에 대한 인덱스는 태울 때마다 증가하게 되고, 방문 처리를 해야 한다.

방문 배열을 따로 만들거나 2중 반복문을 사용하는 대신 투포인터로 퉁쳤다.

무조건 보트 수는 증가하게 되므로, 둘을 함께 태울 수 있을 때만 offset(가장 가벼운 사람 인덱스)을 증가시킨다.

 

(근데 이게 그리디가 맞나...? 그리디 쥐약이라 그냥 투포인터로 풀었다)

코드

import java.util.*;

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

        Arrays.sort(people);

        for(int i = people.length - 1; i >= offset; i--) {
            if(people[i] + people[offset] <= limit) offset++;
            answer++;
        }

        return answer;
    }
}