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

문제

https://programmers.co.kr/learn/courses/30/lessons/42885#

코딩테스트 연습 - 구명보트

풀이

프로그래머스는 문제를 꼼꼼히 읽어야 한다!

구명 보트의 최대 인원이 2명인 것을 간과하고 구현하는 바람에 시간 낭비를 한참 했다. 

 

예시 1)

limit: 100

[50, 30, 70, 50]

 

people을 오름차순으로 deque에 넣는다. 

30, 50, 50, 70

가장 큰 값과 가장 작은 값을 더한다. 

70 + 30 

더한 값이 limit보다 같거나 작다면 구명보트 count 를 증가 시켜주고 두 개의 값을 deque에서 제거한다. 

더한 값이 limit보다 크다면 구명보트 count를 증가시켜주고 가장 큰 값만 deque에서 제거한다.

deque가 empty될때까지 반복한다. 

만약 deque의 size가 1일 때는 짝이 없으므로, count를 증가시키고 반복문을 종료한다. 

 

70, 30 구명보트 +1

50, 50 구명보트 +1

최소 구명보트 2개 

 

예시 2)

limit: 100

[70, 50, 80, 50]

 

-> [ 50, 50, 70, 80]

80  구명보트 +1

70  구명보트 +1

50+50 구명보트 +1

최소 구명보트 3개

 

소스코드

import java.util.*;
class Solution {
    public int[] people;
    public int limit;
    
    public int solution(int[] people, int limit) {

        Arrays.sort(people);
        Deque<Integer> dque = new ArrayDeque<Integer>();
        for(int p : people){
            dque.offer(p); 
        }
        
        int cnt = 0;
        while(!dque.isEmpty()){
            if(dque.size() == 1){
                cnt++; 
                break;
            }
            int last = dque.peekLast();
            int first = dque.peekFirst();

            if(last + first >= limit){
                if(last + first == limit) {
                    dque.removeFirst();
                }
                dque.removeLast();
            } else {
                dque.removeFirst();
                dque.removeLast();
            }
            cnt++;
        }
        return cnt;
    }
}