[프로그래머스/greedy/level2] 구명보트

[프로그래머스]구명보트

핵심 유형

• 정렬과 그리디를 이용한 최소 보트 수 반환

문제 핵심 전략

1. 오름차순으로 정렬한 후, 가장 무거운 사람과 가장 가벼운 사람의 무게 합을 계산한다.

   • 만약 무게가 초과할 경우, 필요한 보트 수를 추가한다. (boatCount++)

   • 만약 두 사람의 무게를 수용할 수 있다면, 함께 탑승을 시키고, 가벼운 사람의 인덱스를 증가시킨다.

오답 노트

1. 반복문을 순회하면서 가벼운 사람의 인덱스까지 포함해야 모든 연산이 이루어지는데 해당 조건을 빼먹어서 디버깅을 하는데 시간이 좀 걸림.

느낀 점

• 그리디의 가장 대표적인 동전 문제와 맥락을 아주 유사한 형태라서 비슷한 형태의 로직으로 문제를 해결해 나갔다.

학습한 내용

• 문제 형태가 투포인터 문제와 유사해서 투포인터에 대해 간단히 살펴보았다.

• 투포인터 : 두 개의 포인터를 사용해서 원하는 해를 빠르게 찾아갈 수 있는 과정

  1. 문제에 따라 O(N^2)를 O(N)으로 시간 복잡도를 개선할 수 있습니다.

  2. 투포인터 방식 : 같은 시점에서 순차적으로 이동시키는 방법과 양 끝점에서 범위를 좁혀나가는 방법이 존재한다.

  3. 슬라이딩 윈도우 방식은 두 개의 포인터를 사용하는 것은 같지만 포인터의 범위가 고정되서 값을 탐색하는 차이가 있다.

  4. 관련 문제

     • 백준 - 수들의 합2

     • leetcode - Container With Most Water

문제 풀이 코드

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);

        int boatCount = 0;
        int lightIdx = 0;
        for (int heavyIdx = people.length - 1; heavyIdx >= lightIdx; heavyIdx--) {
            int sum = people[heavyIdx] + people[lightIdx];
            if (sum <= limit) {
                lightIdx++;
            }
            boatCount++;
        }

        return boatCount;
    }
}