[알고리즘] 구명 보트

포인트 

• 투 포인트 알고리즘 을 쓸 수 있는가? => 대부분 정렬을 사용하는 것이 신상에 매우 좋다.
  
  
• 자신이 원하는 것을 포인터로 둘 수 있는 생각은 좋다. 

cpp/c++

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int solution (vector<int> people, int limit) {
    int answer=0;
    int left=0;
    int right=people.size () - 1; //오른쪽 끝
    sort (people.begin (), people.end (), greater<> ());  // 내림차순

    while (left <= right) { // 투포인터 알고리즘 왼쪽 오른쪽 탐색
        if (people[left] + people[right] <= limit) //2명이 타는거
            right-=1;
        left+=1;
        answer+=1; //무조건 태우는 경우를 가정을 한다. 
    }

    return answer;
}

python

def solution(people: list, limit: int) -> int:
    answer = 0
    people.sort()  # 정렬을 한다. 투포인터를 위해서
    left = 0
    right = len(people) - 1
    while left <= right:
        if people[left] + people[right] > limit:
            # 리미트를 넘는 경우 1개가 더 필요하다.
            # 그리고 1을 줄인다.
            right -= 1
        else:
            # 안넘으면
            left += 1  # 왼쪽 증가
            right -= 1  # 오른쪽 감속
        answer += 1

    return answer


print(solution([70, 50, 80, 50], 100))
print(solution([70, 80, 50], 100))