[프로그래머스] 구명보트 (C++)

그리디 (Greedy)

최대 두명이 탈 수 있으며, limit 만큼의 무게를 감당할 수 있는 구명보트가 있고, N명의 사람들의 무게를 담은 배열이 하나 주어진다. 이때 최소 필요한 구명보트 수 구하기

 

접근방법

힌트를 얻어서 투포인터로 풀었다. 우선 배열을 오름차순으로 정렬하고,

왼쪽 포인터 s, 오른쪽 포인터 e 를 배열 양 끝을 가리키도록 한 다음

두 포인터가 교차될 때 까지 반복하는 반목문을 들어간다.

이 반복문에서는

1) 두 포인터가 가리키고 있는 값을 더했을 때 limit 이하이면, 둘다 보트에 탈 수 있으므로 두 포인터 모두 안쪽으로 옮긴다.

2) 그러나 더한 값이 limit을 초과하면, 무게가 더 많이 나가는 사람만 탈 수 있다는 의미이므로 오른쪽 포인터 (e) 만 한칸 앞으로 옮긴다. (구명보트 limit은 무게가 가장 많이 나가는 사람의 무게 이상이므로 둘 중 한명은 반드시 탈 수 있다)

3) 그리고 두 경우 모두 보트 개수는 증가한다.

 

오답노트

첨에 그냥 정렬해서 풀다가 (작은 것부터 담으면 최소 구명보트 수를 만족할 수 없어서..) 우선순위 큐로 풀어보려고 난리치다가

결국 힌트를 얻어서 투포인터로 풀었는데, 보트에 여러명 들어갈 수 있다고 생각하고 풀어서 후반부 케이스 5개 정도 틀리고,

마침내 최대 두명이라는걸 깨닫고 통과했다..ㅎ

 

소스코드

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

using namespace std;

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

 

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

프로그래머스