[Programmers - 자바] 구명보트

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

코딩테스트 연습 - 구명보트

 

누가 봐도 그리디 하다.

 

두명씩만 탈 수 있는 제한 조건때문에 투 포인터 식으로 풀어보았다.

 

코드를 보자.

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        long sum = 0;
        int lc=0;
        int rc = people.length - 1;
        
        Arrays.sort(people);
        
        while(rc>=lc){
            sum = people[rc] + people[lc];
            
            if(sum>limit){
                rc--;
                answer++;
            }
            else{
                rc--; lc++;
                answer++;
            }
        }
        
        return answer;
        
    }
}

우선 sum 을 구하는데 sum 이 limit 을 넘으면 무거운 친구는 혼자 타야한다. 그래서 rc-- 해주고 answer++ 해준다.

limit 을 안넘으면 둘이 같이 타면 된다. 이 둘이 같이 타는게 왜 최선의 선택인지 좀 어렴풋이 알겠는데 그리디한 문제는 일단 믿고 가야한다.