28. 구명보트

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

구명보트
탐욕법(Greedy)
3171명 완료

이 정도 스포는 해도 될 것 같아서.. 
[40,50,60,70,80,90,100,110,120,130], 170 은 5회다. 

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

파이썬

deque는 double linked list이다. 

from collections import deque


def solution(people: list, limit):
    people.sort()
    que = deque(people)
    answer = 0
    while que:
        if len(que) == 1:
            answer += 1
            break
        if que.pop() + que[0] <= limit:
            que.popleft()
        answer += 1
    return answer

테스트 1 〉	통과 (9.54ms, 10.7MB)
테스트 2 〉	통과 (11.03ms, 10.8MB)
테스트 3 〉	통과 (10.16ms, 10.7MB)
테스트 4 〉	통과 (11.50ms, 10.8MB)
테스트 5 〉	통과 (10.82ms, 10.6MB)

투 포인터라는 기법이다. 
자료를 지우는 시간을 절약할 수 있어 더 빠르다. 

def solution(people, limit):
    people.sort()
    answer, left, right = 0, 0, len(people) - 1
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1
        right -= 1
        answer += 1
    return answer

테스트 1 〉	통과 (8.56ms, 10.5MB)
테스트 2 〉	통과 (9.60ms, 10.5MB)
테스트 3 〉	통과 (8.33ms, 10.5MB)
테스트 4 〉	통과 (8.72ms, 10.6MB)
테스트 5 〉	통과 (8.53ms, 10.5MB)

 

Java

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        Arrays.sort(people);
        var answer = 0;
        var left = 0;
        var right = people.length - 1;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            answer++;
        }
        return answer;
    }
}

https://www.youtube.com/watch?v=rI8NRQsAS_s