[c++] 프로그래머스 - 구명보트(Level 2)

문제

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

 

코드

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

int solution(vector<int> people, int limit) {
    int answer = 0;
    priority_queue<int,vector<int>,greater<int>> pq;    // 최소 힙
    sort(people.begin(),people.end(),greater<>());  // 내림차순 정렬
    
    for(int i=0; i<people.size(); i++){
        if(pq.empty()) pq.push(people[i]);
        else{
            if(people[i]+pq.top()<=limit){
                pq.pop();
                answer++;
            }
            else pq.push(people[i]);
        }
    }
    return answer+pq.size();
}

 

풀이(20분)

구명보트는 작아서 한 번에 최대 2명씩밖에 탈 수 없다.라는 조건을 읽지 않고, 무게 제한만 제약을 주어 구하다가 계속 75점만 떠서 시간을 소비했습니다. -문제를 제대로 읽읍시다-

people	limit	return
[70, 50, 80, 50]	100	3

위 입력을 예시로 한번 설명해보겠습니다.

1. people 배열을 내림차순으로 정렬한다. [80, 70, 50, 50]
2. heap은 최소 힙이다.
3. 현재 heap이 비었기 때문에 하나를 넣는다 pq = [80, ]
4. 70을 pq의 top인 80과 더했을 때 무게 제한 100을 넘어가기 때문에 pq에 push한다. pq = [70, 80, ]
5. 50을 pq의 top인 70과 더했을 때 무게제한 100을 넘어가기 때문에 pq에 push한다. pq=[50, 70, 80, ]
6. 50을 pq의 top인 50과 더했을 때 무게제한 100 이하를 만족하고, 한 보트에 두 명 이상은 탑승할 수 없기에 pop을 하고 구명보트의 개수를 ++해준다. pq = [70, 80]
7. 최종적으로 answer와 남아있는 사람인 pq의 사이즈를 더해주면 필요한 구명보트의 개수가 된다.