C++ / 프로그래머스 / 구명보트

문제

 

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

프로그래머스

문제풀이

 

최대 2명이란 점을 못 보고 풀다가 삽질했다..

lower_bound를 이용해서 풀어봤는데 효율성에서 시간초과가 나서 방법을 바꿨다.

투포인터 알고리즘을 사용해 풀었다.

오름차순이든 내림차순이든 상관은 없지만 오름차순으로 풀었다.

굳이 두 사람의 합을 limit에 가까이할 필요가 없다.

최대 2명이 탈 수 있고, 정렬을 했기 때문에 반례가 나올 수 없다.

 

가장 가벼운 사람과 가장 무거운 사람을 태운다.

만약에 태울 수 없으면 무거운 사람을 혼자 태운다.

가장 가벼운 사람을 태웠으면 ++left를, 가장 무거운 사람을 태웠으면 --right 해서

left가 right가 될 때까지 반복하면 된다.

 

 

코드

 

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit) {
    int answer(0), left(0), right(0);

    sort(people.begin(), people.end());

    right = people.size() - 1;

    while (left <= right) {
        if (left == right) {
            ++answer;
            return answer;
        }
        else if (people[left] + people[right] <= limit) {
            ++left;
            --right;
        }
        else if (people[left] + people[right] > limit) {
            --right;
        }
        ++answer;
    }
    return answer;
}