[프로그래머스] 42885번 / Java / 구명보트 - 그리디

문제 - (https://programmers.co.kr/learn/courses/30/lessons/42885)

사용할 변수의 범위가 1~50000 이어서 한 명마다 완전탐색을 해서 구명보트에 탈 수 있는지 여부를 판단하는 것은 무리가 있다고 생각했다.

곰곰이 생각해보니,

people 배열을 오름차순 정렬한 뒤, 가장 처음 사람과 마지막 사람의 합에 따라 처리해주면 될 것 같다는 생각을 했다.

왜냐면 이미 정렬된 배열이므로, 첫 사람은 몸무게가 가장 적게 나갈 것이고 마지막 사람은 몸무게가 가장 많이 나갈 것이기 때문에

첫사람과 마지막 사람의 몸무게 합이 limit를 넘으면 그 이후 사람은 더 계산해볼 필요도 없이 limit를 넘을 것이기 때문이다.

 

---

📌주의할 점

• 더해서 limit를 넘는 경우, 넘지 않는 경우, 동일한 경우에 어떻게 처리해야할 지 고민해본다.
• 실제 코딩테스트에서는 테스트 케이스 채점 결과만 보여줄 수 있으므로 스스로 테스트 케이스를 추가해서 검증해보는 과정도 필요하다고 생각한다.

---

😅실수

• 배열을 조회하는 연습을 더 해야겠다. 배열 조회만으로 충분히 풀 수 있는 문제인데 굳이 리스트를 사용해서 "시간초과"가 발생했다.

 

---

코드

import java.util.Arrays;

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

        Arrays.sort(people);

        int left = 0;
        int right = people.length - 1;

        while (left != right && left < right) {
            int weight = people[right];
            for (int i = left; i < right; i++) {
                weight += people[i];
                if (weight == limit) {
                    left = i + 1;
                    right--;
                    answer++;
                    break;
                } else if (weight > limit) {
                    left = i;
                    right--;
                    answer++;
                    break;
                }else {
                    if (i == right - 1) {
                        // 마지막까지 더했는데도 limit보다 작으면
                        left = i;
                        right--;
                    }
                }
            }
        }

        return left == right ? answer + 1 : answer;
    }
}