프로그래머스 lv2 - 구명보트 (자바)

문제

---

프로그래머스 lv2 - 구명보트

풀이

---

내 풀이
정합성 테스트는 다 통과했지만 효율성 테스트를 전부 시간 초과로 실패했다.

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);

        for (int i = 0; i < people.length; i++) {
            if (people[i] == 0) continue;
            int w = people[i];
            int mx = 0;
            int idx = 0;
            for (int j = i + 1; j < people.length; j++) {
                if (people[j] == 0) continue;
                if (w + people[j] <= limit && w + people[j] > mx) {
                    mx = w + people[j];
                    idx = j;
                }
            }
            people[idx] = 0;
            answer++;
        }

        return answer;
    }
}

옳은 풀이

• 몸무게 무거운 순으로 오름차순 정렬 후 가장 무거운 사람과 가장 가벼운 사람을 태우면 됨
• 그리디 문제는 설마 이게 된다고? 싶은 느낌이 드는 방법으로 풀리는 경우가 많음

어려웠던 점

---

그리디 문제는 재능의 영역인가...
그리디 문제는 사고를 떠올리는 것이 너무 힘들다.

코드

---

정답 코드

import java.util.*;
class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        Arrays.sort(people);

        int idx = 0; // 가장 가벼운 사람
        for (int i = people.length - 1; i >= idx; i--) {
            if (people[i] + people[idx] <= limit) { // 가장 무거운 사람 + 가장 가벼운 사람 <= limit
                idx++;
                answer++;
                continue;
            }
            answer++; 
        }

        return answer;
    }
}

참고

---

도저히 효율성 테스트를 뚫을 방법이 생각이 나지 않아서 프로그래머스 다른 사람의 풀이 참고했다.