[프로그래머스] 자바(Java) - 구명보트

🧩 문제

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

프로그래머스

 

💡내가 작성한 코드

⭐️ 제한된 무게를 가진 구명보트를 사용하여 최대한 많은 사람을 효율적으로 구축하는 것이 목적

• 최적의 선택을 하기 위해 최대한 무게가 무거운 사람과 가벼운 사람을 함께 태워야 함

import java.util.*;

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

 

1. `people[]` 배열을 오름차순으로 정렬
   • 무게가 무거운 사람과 가벼운 사람을 쉽게 짝지을 수 있도록 정렬
2. 무게가 가벼운 사람(`index`)과 가장 무거운 사람(`int i`)을 짝지을 수 있도록 변수 설정
   • 무거운 사람을 기준으로 반복문을 실행하는 이유는 탐욕법의 원칙 중 하나인 "현재 상황에서 최적의 선택" 을 따라야 하기 때문에, 제한 무게에 가장 큰 영향을 미치는 무거운 사람을 기준으로 반복문 실행
   • 무거운 사람을 기준으로 진행하면, 그와 함께 태울 수 있는 가벼운 사람을 찾아내기 용이
   • 무거운 사람을 나중에 처리할 경우, 제한 무게를 초과하게 되어 불필요한 보트를 더 사용해야 될 경우가 생김
3. 선택한 가벼운 사람과 무거운 사람이 `limit` 조건을 충족하는지 확인
   • `limit`을 넘지 않을 경우, 두 사람을 태울 수 있는 조건을 충족시키는 것이기 때문에 `answer` 증가시키고, `index`를 증가시켜 다음 태울 사람의 인덱스를 지정
   • `limit`을 넘을 경우, 보트를 보내야하기 때문에 `answer` 증가
4. 모든 사람을 태울 때까지 반복 후, answer return

 

🧠 배운 점

이 문제를 풀면서 탐욕법이 무엇인지, 그리고 어떠한 상황에서 탐욕법을 사용하는 것이 적절한지 알게 되었다.

1. 탐욕법의 정의와 최적의 선택을 위한 기준 설정
   • 탐욕법은 매 순간마다 최적의 선택을 하여 문제를 해결하는 알고리즘
   • 최적의 선택을 위해, 가장 무거운 사람을 기준으로 선택하여 최적의 값을 도출할 수 있었음