[코테연습] 구명보트

    오늘 문제는 탐욕법 - 구명보트 문제이다.

    이 문제는 문제를 잘 이해한다면, 어렵지 않은 문제라고 생각한다.

    중요포인트는 구명보트를 최대한 적게 사용해야한다는 점이다.

    단순하게 생각하면 [40,50,50,60,70] // limit : 100 이라는 숫자가 주어졌을때

    가장 몸무게가 작은 사람 40, 50, 을 구출하고
    이후 50 // 60 // 70 을 구출하여 4번 왕복하면 된다.
    하지만 구명보트를 최대한 적게 사용하는 방법은 아니다.

    구명보트를 최대한 적게 사용하는 방법은 40, 60 // 50, 50 // 70 이다.
    즉 몸무게가 가장 적은 사람이 먼저 타고 몸무게가 가장 많은 사람 중에서 같이 탔을 때 limit 에 걸리지 않은 사람이다.
    
    이것을 논리적으로 풀이하면 다음과 같다.


     1. 사람 몸무게 배열 Dqueue 에 담는다.
     2. Deque 을 오름차순으로 정렬한다.
     3. 가장 적은 수를 pick 한다. (first)
     4. 가장 많은 수 (last)에서 limit 보다 작거나 같을때까지 뽑는다.
     5. 버려지는 수만큼 count 한다
     6. 가장 적은 수+가장 많은 수 가 limit 보다 작으면 count 를 한개만 늘린다.
     7. Dqueue 가 empty 일때까지 반복한다.
    
    
    Dequeue 를 이용하였으며, 코드로 구현하면 다음과 같다.

 

 

public int solution(int[] people, int limit) {

        int answer = 0;

        Arrays.sort(people);

        Deque<Integer> deque = new LinkedList<>();

        for (int i = 0; i < people.length; i++) {

            deque.offer(people[i]);

        }

        int count = 0;

        while(!deque.isEmpty()) {

            int first = deque.pollFirst();

            while(!deque.isEmpty()) {

                int last = deque.pollLast();

                System.out.println("deque : "+deque+ "// ["+first+", "+last+"]");

                if (first+last <= limit) {

                    break;

                }

                count++;

            }

            count++;

        }

        System.out.println("count : "+count);

        answer = count;

        return answer;

    }