프로그래머스 - 구명보트 (Level2, Greedy)

우선 그리디 알고리즘 문제이다.

문제는 아래와 같다.

 

문제에서 보트에 최대 2명씩 밖에 탈 수 없다는 조건이 있기 때문에 나는 투포인터 알고리즘을 사용해서 문제를 풀고자 했다.

 

투포인터 알고리즘이란, 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘이다.

즉 포인터를 두개로 설정하면 된다.!

풀이 코드

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

using namespace std;

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

    sort(people.begin(), people.end()); // 오름차순 정렬부터 해주기
    
    int tmp = 0;

    int f_idx = 0; // 앞에서 시작
    int b_idx = people.size() - 1; //뒤에서 시작

    while(f_idx <= b_idx){
        if(people[f_idx] + people[b_idx] <= limit){
            f_idx++; 
            b_idx--;
        }else{
            b_idx--;
        }
        answer++;
    }

    return answer;
}