개요

프로그래머스 구명보트

• 문제 설명
  무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.

  예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.

  구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.

  사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

• 제한사항
  무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
  각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
  구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
  구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

접근 방식

1. 처음엔 단순하게 벡터를 정렬하고 작은 것부터 실어 날랐다.
   이렇게 풀면 안 되는 이유는 보트에 최대 2개만 들어가기 때문이다.
   예를들어 limit가 200인데 무게가 40짜리 두 개가 있다면 40,40 이렇게
   실어서 무게가 낭비된다.

2. 두 번째 접근 방식은 제일 무거운 인간과 제일 가벼운 인간을 뽑아서
   보트로 나르기였다.
   어차피 제일 무거운 인간은 보트에 혼자탈 확률이 높다.
   따라서 제일 가벼운 인간을 보트에 같이 태워본 후, 탈 수 있다면 같이 태운다.

   인간을 보트에 태운다면 벡터에서 erase하는 식으로 구현했으나,
   인간의 수가 최대 50000명으로 큰 편이라 그런지, 시간초과가 났다.
   

3. 벡터에서 erase함수를 호출해서 시간이 많이 걸리는 것 같아서
   erase함수 대신 iterator을 두개 사용해서 풀었다.

   시작 iterator과 끝 iterator을 잡고, 무거운 인간을 빼면 끝iterator--,
   가벼운 인간을 빼면 시작iterator++하는식으로 구현했다.

   while(startIter<=endIter){
         //제일 무거운 친구 일단 태움
         boatWeight+=(*endIter);
         //제일 가벼운 친구 태워봄
         boatWeight+=(*startIter);
         
         //가벼운 친구 태웠을 때 무게가 총합 넘어가면
         if(limit<boatWeight || people.size()==1) {
             answer++;
             //무거운 친구만 태움
             endIter--;
             boatWeight=0;
             continue;
         }
         //둘다 태움
         answer++;
         boatWeight=0;
         endIter--;
         startIter++;
     }

   iterator 두개가 서로 교차되면 모든 인원을 태운 것으로 판단해
   종료한다.

전체 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0,boatWeight=0;
    vector<int>:: iterator startIter=people.begin(),endIter=people.end()-1;
    sort(people.begin(),people.end());

    while(startIter<=endIter){
        //제일 무거운 친구 일단 태움
        boatWeight+=(*endIter);
        //제일 가벼운 친구 태워봄
        boatWeight+=(*startIter);
        
        //가벼운 친구 태웠을 때 무게가 총합 넘어가면
        if(limit<boatWeight || people.size()==1) {
            answer++;
            //무거운놈 한명 보냄
            endIter--;
            boatWeight=0;
            continue;
        }
        //둘다 보냄
        answer++;
        boatWeight=0;
        endIter--;
        startIter++;
    }
    return answer;
}

문풀후생

다른사람의 풀이

iterator을 두 개 사용하여 풀었지만,
그냥 반복문을 이용해 index만 가지고 풀 수도 있었다.

벡터를 내림차순으로 정렬한 후, int i는 0부터 int j는 벡터사이즈-1부터 시작한다.
내림차순 정렬이라 i가 무거운 녀석을 가리키고 j가 가벼운 녀석을 가리킨다.

그 다음 과정은 내 풀이와 비슷하다.

매 반복문마다 i를 증가시켜 무거운녀석을 하나씩 보낸다.

people[i]+people[j]값이 limit보다 작거나 같으면
j를 증가시켜 가벼운 녀석도 하나 보낸다.

다른 풀이 코드

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

using namespace std;

int solution(vector<int> people, int limit) {
    int answer = 0,peopleAmount=people.size();
    sort(people.begin(),people.end(),greater<int>());
    
    //매 반복문당 무거운녀석 한명씩 보냄
    for(int i=0,j=peopleAmount-1; i<=j;i++){
        //가벼운녀석과 무거운녀석을 더했을 때 limit안넘기면
        if(people[i]+people[j]<=limit){
            //가벼운녀석 보냄
            j--;
        }
        answer++;
    }
    return answer;
}