[Lv 2] 구멍보트

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

프로그래머스

 

이 문제는 투포인터를 사용해서 해결할 수 있다.

문제에서 보트는 최대 2명만 탑승할 수 있으며, limit 이하인 경우에만 보트에 탑승할 수 있다는 것을 알려준다.

따라서 무게 순으로 배열을 정렬을 해야한다.

이후 left 포인터는 가장 작은 무게부터 시작하고 right 포인터는 가장 높은 무게부터 시작하며 반복을 시작한다.

두개의 포인터가 가리키는 무게의 합이 limit보다 작으면 두 개의 포인터를 이동시키고 보트 수를 증가시킨다.

limit보다 큰 경우 다른 작은 무게를 찾기 위해 right 포인터만 이동시키고 보트 수를 증가시킨다.

 

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

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