[탐욕법] 구명보트

public static int solution(int[] people, int limit) {
        int answer = 0;

        Arrays.sort(people);
        ArrayDeque<Integer> dq = new ArrayDeque<>();
        for (int person : people) {
            dq.add(person);
        }

        while (!dq.isEmpty()) {
            if(dq.peekFirst() >= limit) {
                answer = dq.size();
                break;
            } else {
                int able = limit - dq.peekLast();
                if (dq.peekFirst() <= able) {
                    dq.pollFirst();
                    dq.pollLast();
                    answer++;
                } else {
                    dq.pollLast();
                    answer++;
                }
            }
        }

        return answer;
  }

내가 생각한 방법은 내림차순으로 정렬해서 반복문을 돌린 후 가장 가벼운 무게와 더해 한 보트에 탈 수 있는지 체크하고 큐에서 빼내주고 못타면 새보트에 태우는 식이었다

			if(dq.peekFirst() >= limit) {
                answer = dq.size();
                break;
            } 

처음에 이 부분없이 코드를 돌렸더니 효율성에서 통과를 못했는데 이 부분 추가해주었더니 통과했다
제일 적은 무게가 한계를 넘어버리면 비교를 할 필요가 없으니 배열의 사이즈가 곧 보트의 수이다

이번 문제 풀면서 사용한건 deque 이다 기존 큐와 사용법이 매우 유사했는데 어떤 쪽으로 입력하고 어떤 쪽으로 출력하느냐에 따라서 스택(Stack)으로 사용할 수도 있고, 큐(Queue)로도 사용할 수 있다.

삽입
addFirst() - 덱의 앞쪽에 엘리먼트 삽입
offerFirst() - 덱의 앞쪽에 엘리먼트 삽입
addLast() - 덱의 마지막 쪽에 엘리먼트 삽입
offerLast() - 덱의 마지막 쪽에 엘리먼트 삽입
add() - addLast()와 동일

addAll(Collection<E> c) - 입력받은 c의 모든 데이터를 덱의 뒷쪽에 삽입
push() - addFirst()와 동일(덱을 스택으로 사용할 때 쓰임)

삭제
removeFirst() - 덱의 첫번째에서 엘리먼트 하나를 제거 후 출력
pollFirst() - 덱의 첫번째에서 엘리먼트 하나를 제거 후 출력
removeLast() - 덱의 마지막에서 엘리먼트 하나를 제거 후 출력
pollLast() - 덱의 마지막에서 엘리먼트 하나를 제거 후 출력
remove() - removeFirst()와 동일
poll() - pollFirst()와 동일

removeFirstOccurrence(Object o) - 덱의 앞쪽부터 탐색하여 입력한 o와 동일한 첫 엘리먼트 제거
removeLastOccurrence(Object o) - 덱의 뒷쪽부터 탐색하여 입력한 o와 동일한 첫 엘리먼트 제거
element() - removeFirst()와 동일
remove(Object o) - removeFirstOccurrence(Object o)와 동일

pop() - removeFirst()와 동일(덱을 스택으로 사용할 때 쓰임)

출력
getFirst() - 덱의 첫번째 엘리먼트 리턴
peekFirst() - 덱의 첫번째 엘리먼트 리턴
getLast() - 덱의 마지막 엘리먼트 리턴
peekLast() - 덱의 마지막 엘리먼트 리턴
peek() - peekFist()와 동일

기타
contain(Object o) - 덱에 o와 동일한 엘리먼트가 포함되어 있는지 확인
size() - 덱의 크기
iterator() - 덱의 앞쪽부터 순차적으로 실행되는 이터레이터 얻음
descendingIterator() - 덱의 뒷쪽부터 순차적으로 실행되는 이터레이터 얻음