[프로그래머스] 구명보트 for JAVA _ 그리디 알고리즘

 

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

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

 

 

 

문제

 

 

 

---

 

people[] 배열이 뒤죽박죽 되어있으므로 Arrays.sort()를 이용해 오름차순으로 정리한다.

 

그리고 여기서 가장 큰 수는 people.length() - 1 인덱스를 가진 수 이다. 맨 뒤에꺼!

 

얘랑 people[0] 인 가장 작은 수와 더했을 때 limit보다 작으면 둘이 태울 수 있고

 

limit보다 크다면 뚱뚱이 한명만 태울 수 있다.

 

 

뚱뚱이를 한명 태우고 개말라의 인덱스는 0으로 그대로 둔다.

 

여기서 포인트는 뚱뚱이는 차례대로 무조건 태워버린다는 점이다! 말라도 태울 수 있으면 좋고 아님 말고~

 

 

그래서 2중 for문을 사용하지는 않고... 따로 개말라 index인 j를 선언해주었다.

 

 

 

 

코드

import java.util.Arrays;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        int j = 0;
        Arrays.sort(people);
        
        for(int i = people.length - 1; i >= j; i--){
            if(people[i] + people[j] <= limit) j++;
            answer++;
        }
        return answer;
    }
}

 

 

다른 사람꺼 살짝 참고했다. 슬픈 현실....

 

 

 

성능

 

 

 

---

 

다른 사람 코드

 

 

 

 

 

다들 비슷하게 풀었구나