[프로그래머스 Lv2] : 구명보트

문제 링크

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

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

무인도에 갇힌 사람들을 모두 구하기 위해 필요한 최소 구명보트 수를 리턴하는 문제.

 

풀이

보트에는 최대 2명의 사람이 탈 수 있으며, 무게 제한이 있다.

• 풀이 알고리즘

 무게가 가벼운 사람은 최대한 무게가 무거운 사람이랑 같이 타야 최대한 많은 사람들이 짝을 이뤄서 보트에 탈 수 있다.

일단 탈출해야할 사람들을 무게순으로 정렬해준다.

투포인터 방식을 이용해서 나가야할 사람중 가장 가벼운 사람 한 명(이하 L)과 가장 무거운사람 한 명(이하 R)을 가리킨다.

만약 두 사람의 무게 합이

1. limit보다 크면 : 무게를 줄여야하므로 현재 가리키고있는 R을 한 칸 앞으로 당긴다. R = R - 1.

2. limit보다 작거나 같으면 : 같이 보트를 탈 수 있으므로 두 사람을 탑승시킨다. L = L + 1, R = R - 1.

이 과정을 L과 R이 같아지기 전까지 반복한다.

L >= R인 경우는 L은 가벼운 사람을 R은 무거운 사람을 가리킨다는 기준에 모순되므로 이때는 더 이상 짝을 지을 수 있는 인원이 없다고 판단하고 반복문 종료.

=> 탑승하지 못한 사람들은 혼자서 탑승한다.

 

코드 작성

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_N = 50000 + 5;
bool is_escaped[MAX_N];
 
int solution(vector<int> people, int limit) {
    int answer = 0;
    sort(people.begin(), people.end());
    int L = 0; int R = people.size() - 1;
    for(int i = 0; i<people.size() - 1; i++){
        if(people[L] + people[R] <= limit){
            is_escaped[L] = is_escaped[R] = true;
            L++, R--;
            answer++;
        }
        else R--;
        if(L >= R)
            break;
    }
    for(int i = 0; i<people.size(); i++)
        if(!is_escaped[i])
            answer++;
    return answer;
}