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

https://programmers.co.kr/learn/courses/30/lessons/42885?language=cpp 

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

---

 

-풀이-

무거운 사람부터 태운다. 무거운 사람부터 태울때, 가벼운사람을 껴넣어서 같이 탈 수 있다면 같이 태워 보내면되고, 안되면 무거운 사람만 태워 보내면된다.

왜 제한을 넘기면 무거운 사람만 태워 보내냐면, 가벼운사람은 남겨둔다면 가벼운 사람 2명씩 탈 수 있는 경우가 나오기때문에, 최소한의 구명보트를 사용하기 위해선, 제한을 넘긴다면 무거운 사람을 한보트에 태워보내야한다.

 

-시간복잡도-

정렬에 O(NlogN)이 소모된다. 따라서 O(NlogN)이 된다.

 

-코드-

C++

//c++ 오름차순 정렬 풀이
#include <vector>
#include<algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(),people.end());
    int left=0;
    int right=people.size()-1;
    while(left<=right){
        if(people[left]+people[right]<=limit){
            left++;
        }
        right--;
        answer++;
    }
    return answer;
}

 

Python

#python3 내림차순 풀이
def solution(people, limit):
    answer = 0
    people.sort(reverse=True)
    left=0
    right=len(people)-1
    
    while(left<=right):
        answer+=1
        if(people[left]+people[right]<=limit):
            right-=1
        left+=1
    return answer

 

JavaScript

//JavaScript 내림차순 풀이
function solution(people, limit) {
    var answer = 0;
    people.sort((a,b)=>b-a);
    var left=0;
    var right=people.length-1;
    
    while(left<=right){
        if(people[left]+people[right]<=limit){
            right--;
        }
        left++;
        answer++;
    }
    return answer;
}