프로그래머스 | LV.2 구명보트 - 그리디 문풀 (Java)

⬛ 프로그래머스 | LV.2 구명보트 - 그리디 문풀 (Java)

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

프로그래머스

문제 설명

---

💚문제 접근 방식

예전에 풀었던 문제를 다시 풀게 됐다.

프로그래머스 | LV.2 구명보트 - 그리디 문풀 (Java)

 

이 문제의 경우 매번 그리디적으로 최소 구명보트를 사용할 수 있는 방법을 사용해야 한다.

매번 최선 : 가장 작은 값 + 가장 큰 값을 최대한 한 번에 처리하는 것.

그런데 그게 Limit보다 작거나 같으면 (두 명을 1개의 구명보트로 처리하는 것이고), Limit을 넘어버리면 한명만 구명보트를 써야 한다. (더 큰애를 쓰는 게 맞음)

st 로 0을 ed로 끝을 지칭하고 st ≤ ed 인 동안 매번 둘이 지칭하는 값의 합이 limit과 큰지 작은지를 비교해가며 구명보트를 사용하면 된다 .

 

1) if(st + ed ≤ limit) {

// 이 경우 limit 이내의 값이므로 1개의 구명보트로 2명을 태운다.

st와 ed도 다음 처리할 idx를 지칭하도록 처리하고 answer++ 처리

2) else (st + ed > limit) {

// 이 경우 어쨋든 큰 애를 구명보트에 태워서 1명만 보낸다.

answer++처리 하고, ed 만 다음 idx를 지칭하도록 처리한다.

→ 이렇게 만들고 나면 정답 처리 된다.

💚 제출 코드

import java.util.*;
class Solution {
    
    //솔루션 함수 
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        int st = 0;
        int ed = people.length-1;
        
        //정렬 오름차순
        Arrays.sort(people);
        
        while(st <= ed){
            if(people[st] + people[ed] <= limit){
                answer++;//구명보트 ++처리 
                st++;//처리 완료하니 다음 찍고
                ed--;//얘도 처리 완료라 다음 찍고
            }else{
                answer++;
                ed--; // 더 큰 거만 처리하고 다음 찍기
            }
        }
        
        return answer;
    }
}