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

코드 힌트

1. 배열을 정렬하여 사용하기:
   • 배열 people을 오름차순으로 정렬합니다. 정렬을 통해 가장 가벼운 사람과 가장 무거운 사람을 쉽게 비교할 수 있습니다.
2. 다중 반복문을 사용하지 않고 투 포인터 알고리즘을 사용하기:
   • 투 포인터 알고리즘을 사용하여 효율적으로 사람들을 보트에 태웁니다.
   • startIdx는 가장 가벼운 사람을 가리키고, endIdx는 가장 무거운 사람을 가리킵니다.
3. 탐욕법으로 조건을 처리하기:
   • 각 단계에서 가장 가벼운 사람과 가장 무거운 사람을 비교하여 보트에 태웁니다.

투 포인터 알고리즘이란?

1차원 배열에서 각기 서로 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 값을 찾을 때까지 탐색하는 알고리즘입니다. 일반적으로 배열의 시작과 끝에서 포인터를 시작하여 서로를 향해 이동하면서 조건을 만족하는 요소를 찾습니다.

탐욕법이란?

각 단계에서 최적이라고 생각되는 것을 선택해 나가는 방식입니다. 항상 최적의 값을 보장하지는 않지만 근사한 값을 목표로 합니다. 간단히 말해, 적당한 조건에 맞으면 해당 조건을 선택한다는 의미입니다.

---

정답은 더보기 클릭

import java.util.*;

class Solution {
    public int solution(int[] people, int limit) {
        int result = 0;
        
        // 오름차순 정렬
        Arrays.sort(people);
        
        // 시작 포인트와 끝 포인트
        int startIdx = 0;   // 가벼운 사람 Index
        int endIdx = people.length - 1;  // 무거운 사람 Index
        
        // startIdx가 endIdx보다 크면 모든 사람이 보트를 탔다는 의미
        while (startIdx <= endIdx) {
            // 만약 제일 가벼운 사람과 무거운 사람을 함께 탈 수 있을 때
            if (people[startIdx] + people[endIdx] <= limit) {
                startIdx++;  // 조건에 맞으면 가벼운 사람이 탔으므로 startIdx를 증가시킴
            }
            
            // 무거운 사람은 항상 보트를 탐
            endIdx--;  
            
            // 보트 사용 횟수 증가
            result++;
        }
        
        return result;
    }
}

탐욕법은 각 단계에서 현재 상황에서 가장 최선이라고 생각되는 선택을 하는 방식입니다. 이 방법이 항상 전체 문제에 대해 최적의 해를 보장하지는 않습니다. 즉, 탐욕법은 최적의 해를 보장하지 않지만, 대부분의 경우에는 좋은 근사 해를 찾을 수 있습니다.

 

따라서 이 문제에서 탐욕법을 사용하면 최적의 해를 찾지 못할 수도 있습니다. 즉, 탐욕법은 최적의 값을 항상 찾는 것은 아니지만, 문제를 효율적으로 해결하는 데 유용할 수 있습니다.

 

이 문제에서 탐욕법을 사용해도 대부분의 경우 좋은 결과를 얻을 수 있지만, 항상 최적의 해를 보장하지 않는다는 것을 염두에 두어야 합니다.