99클럽 코테 스터디 19일차 TIL - [프로그래머스] 구명보트 (Java)

📌 오늘의 학습 키워드

[프로그래머스] 구명보트 (Java)
https://school.programmers.co.kr/learn/courses/30/lessons/42885

📌 공부한 내용 본인의 언어로 정리하기

문제 탐색하기

입력 : 사람들의 몸무게를 담은 배열 people[] / 구명보트의 무게 제한 limit가
출력 : 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값

가능한 시간복잡도

O(nlogn)

알고리즘 선택

그리디

📌 코드 설계하기

1. 사람들의 무게를 나타내는 배열을 오름차순으로 정렬한다. 이는 가장 가벼운 사람과 가장 무거운 사람을 쉽게 쌍으로 묶을 수 있도록 한다.
2. 두 개의 포인터를 사용한다. 하나는 가장 가벼운 사람을 가리키는 lightest 포인터이고, 다른 하나는 가장 무거운 사람을 가리키는 heaviest 포인터이다. lightest는 배열의 시작 지점에서 시작하고, heaviest는 배열의 끝에서 시작한다.
3. lightest와 heaviest가 가리키는 두 사람의 무게 합이 보트의 무게 제한보다 작거나 같으면 두 사람을 한 보트에 태운다. 그런 다음 두 포인터 모두 이동시킨다.
4. 두 사람의 무게 합이 무게 제한을 초과할 경우, 가장 무거운 사람만 보트에 태운다. 이 경우에는 heaviest 포인터만 이동한다.
5. 각 보트에 대해 사용할 때마다 보트의 수를 증가시킨다.
6. 두 포인터가 만날 때까지 위의 과정을 반복한다. 반복이 종료되면 필요한 보트의 최소 개수를 반환한다.

📌 오늘의 회고

어떤 문제가 있었고, 나는 어떤 시도를 했는지

없음

어떻게 해결했는지

없음

무엇을 새롭게 알았는지

내일 학습할 것은 무엇인지

구현

📌 정답 코드

import java.util.*;


class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people); // 1단계: 배열 정렬
        int lightest = 0; // 가장 가벼운 사람을 가리키는 포인터
        int heaviest = people.length - 1; // 가장 무거운 사람을 가리키는 포인터
        int boats = 0; // 필요한 보트 수를 세는 변수

        // 2단계: 투 포인터 기법을 사용하여 사람들을 짝지음
        while (lightest <= heaviest) {
            // 가장 가벼운 사람과 가장 무거운 사람이 함께 탈 수 있는지 확인
            if (people[lightest] + people[heaviest] <= limit) {
                lightest++; // 가장 가벼운 사람 포인터 이동
            }
            heaviest--; // 가장 무거운 사람 포인터 이동
            boats++; // 보트 수 증가
        }

        return boats; // 필요한 보트 수 반환
    }
}