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

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

프로그래머스

 

풀이 과정

오름차순으로 정렬한 뒤, 이분탐색 알고리즘을 써서 맨 앞과 맨 뒤의 무게를 더해  
limit보다 작으면 앞의 사람, 뒤의 사람 2명 같이 구출할 수 있다는 뜻이므로  
left를 +1 해주고, right를 -1 해준다.  
만약 limit보다 크다면, 같이 구출할 수 없기 때문에 뒤의 사람인 right 사람만 탈출한다는 뜻으로 right만 -1 해준다.

left와 right가 같을 때까지 while문을 돌려야  
사람이 50, 70, 80이고 제한이 100일 때 (0, 2)(0, 1)(0, 0)으로 카운트가 3번된다.

 

풀이 1

#include <string>
#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, right = people.size() - 1;
    while(left <= right){
        if(people[left] + people[right] <= limit){
            left++;
            right--;
        }
        else right--;
        answer++;
    }
    return answer;
}

 

풀이 2 - 시간 초과

직접 구현하면 테스트케이스는 다 맞지만,  
효율성테스트에서 시간초과가 난다..!

#include <string>
#include <vector>

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0;
    // sort 오름차순 구현
    for(int i = 0; i < people.size(); i++){
        for(int j = 0; j < people.size() - 1; j++){
            if(people[j] > people[j + 1]){
                int temp = people[j];
                people[j] = people[j + 1];
                people[j + 1] = temp;
            }
        }
    }
    int left = 0, right = people.size() - 1;
    while(left <= right){
        if(people[left] + people[right] <= limit){
            left++;
            right--;
        }
        else right--;
        answer++;
    }
    return answer;
}