프로그래머스(C++) - 최소 직사각형

●문제

 

●입출력

 

문제해석 

people vector안의 원소가 limit제한에 맞춰 사용할수있는 보트의 최소 갯수 구하기

 

푼방법

그리디 알고리즘으로 투포인터를 사용하여 정렬을 사용한뒤 가장 왼쪽인덱스와 가장 마지막 인덱스가 limit보다 작거나 같을때

인덱스가 빌떄까지 인덱스를 증가혹은 감소하여 값 도출

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

using namespace std;
//무게제한, max 2명
int solution(vector<int> people, int limit) 
{
    // [50, 50, 70, 80]
    sort(people.begin(), people.end()); 
    int left_Idx = 0;
    int right_Idx = people.size() - 1;
    int answer = 0;
    //투포인터 그리디 방식
    //인덱스가 빌떄까지 
    while (left_Idx <= right_Idx)
    {
        if (people[left_Idx] + people[right_Idx] <= limit)
        {
            left_Idx++;
            right_Idx--;
        }
        else
        {
            right_Idx--;
        }
        answer++;
    }
    return answer;
}

 

---구현을하며

처음에는 큐를 사용하여 풀었으나 시간복잡도 면에서 너무 손해를 본다

그리디로 푸는게 훨씬 효율적이다