[프로그래머스 / Level_2 / C++] 구명보트

이 문제는 그리디를 활용해서 풀면 되는 문제므로 어떻게 문제에 접근해야할지 잠깐 고민할 시간이 필요하다. 

해당 문제에서 구명보트에는 단 두사람만 탈수 있다는 것에 중점을 두고 풀어야한다. 

 

아무리 몸무게가 낮다고 해도 탈 수 있는 사람은 단 두명! 

 

그렇기 때문에 가장 적절하게 사람들을 태우기 위해서는 

"제일 무거운사람 한명"과 "제일 가벼운사람 한명"을 태워야한다. 

 

왜냐하면 무거운 애들 두명을 태울려고 해도 limit을 넘길 경우가 무조건 있을 것이다. 

그렇기 때문에 최대한 가벼운애 한명 + 무거운애 한명을 태우는게 이 문제에서 요구하는 조건인것이다. 

 

#접근방법 

1. 무게를 담고 있는 벡터 오름차순으로 정렬 

2. 투포인터를 활용하기 위해 시작 포인터 s와 끝 포인터 e를 생성한다. 

3. s가 가리키는 원소와 e가 가리키는 원소의 합이 limit을 넘지 않으면 result값을 1 증가시킨다. (* s,e 포인터 위치 변경)

4. 만약 s가 가리키는 원소와 e가 가리키는 원소의 합이 limit을 넘으면 두명을 못 태우기 때문에 무거운 친구 혼자 태워서 보낸다. 이때도 result값을 1 증가시킨다. 

5. 반복문은 s가 e보다 같거나 작을때 동안 수행하며 만약 s가 e 와 같아진다면 남은사람이 한명이기 때문에 혼자 태워보내고 result 값을 1 증가시키고 반복문을 종료한다. 

 

  

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

int solution(vector<int> people, int limit) {
    int result =0; 
    int s = 0; 
    int e = people.size()-1; 
    sort(people.begin(), people.end()); 
    while(s<=e){
        if(s==e){
            result++; 
            break; 
        }
        else if(people[s]+people[e]<=limit){
            result++; 
            s++; 
            e--; 
        }
        else{
            e--;
            result++; 
        }
    }
    return result;    
}

 

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