[그리디] 프로그래머스 "구명보트"

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

코딩테스트 연습 - 구명보트

수행시간 : 30분 / 난이도 : 레벨 2

 

얼핏보면 일반적인 투포인터 문제라고 생각할 수 있다. 하지만 처음 로직을 짤 때, 문제에서 요구하는 그리디적인 로직이 필요하다.

우선, 소팅을 통해 가장 작은값부터 큰값까지 정렬을 한다.

처음 로직을 짰을때는, 정렬 후 가장 작은값부터 비교해가면서 i번째 + (i+1)번째 의 값이 limit를 초과하는 순간 pivot을 만들어 계산하는 로직을 생각했는데, 테스트케이스에서 반절이나 틀리는 것을 보고,

가장 작은 값부터 비교하는 것이 아닌 가장 작은 값과 가장 큰 값을 엮으면서 진행햐야됨을 깨닭았다.

그럼 가장 작은 값과 가장 큰값을 더해가면서 limit과 비교해주는 가장 대표적인 알고리즘인 "투포인터" 기법을 이용하면 된다. 다만, while문을 break 해줄때, min 값이 max 값보다 커질때 말고도, min값과 max값이 동일해지는 순간. 그 순간에 남은 인덱스는 people[max] = people[min] 값 하나이므로 answer+1 을 해준 상태로 while문을 탈출하면 구현 할 수 있다. 

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int min_val = 0;
    int max_val = people.size()-1;
    //cout << max_val;
    while(min_val < max_val){

        int sum = people[min_val] + people[max_val];
        if(sum > limit){
            max_val--;
        }
        else{
            max_val--;
            min_val++;
        }
        answer++;
        if(max_val == min_val){
            answer++;
            break;
        }
    }

    return answer;
}