[코딩테스트] Java 구명보트

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

그리디 문제는 대부분 정렬과 조합을 이룬 문제가 많습니다. 따라서 가장 무거운 사람과 가장 무게가 작은 사람을 태워야 최대 limit를 채울 수 있습니다.

소스코드

import java.util.*;

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

        return answer;
    }
}

코드 설명

• 초기화
  • answer: 최소 보트 수를 저장하는 변수로 초기값은 0입니다.
  • index: 가장 가벼운 사람의 인덱스를 나타내는 변수로 초기값은 0입니다.
  • Arrays.sort(people): people 배열을 오름차순으로 정렬하여 무게가 가벼운 사람부터 무거운 사람 순으로 정렬합니다.
• for (int i = people.length - 1; i >= index; i--) { if (people[i] + people[index] <= limit) { index++; } answer++; }
  
  • i는 가장 무거운 사람의 인덱스를 가리킵니다. i는 배열의 끝에서 시작하여 index까지 감소합니다.
  • if (people[i] + people[index] <= limit): 가장 무거운 사람(people[i])과 가장 가벼운 사람(people[index])의 합이 limit 이하인지 확인합니다.
    • 조건이 true인 경우, 두 사람을 한 보트에 태울 수 있으므로 index를 1 증가시켜 다음으로 가벼운 사람을 가리키도록 합니다.
  • answer++: 보트를 사용한 횟수를 증가시킵니다. 무거운 사람(people[i])은 항상 보트에 태워지므로 answer는 무조건 증가합니다.
• return answer;
  • 최소 보트 수를 반환합니다.