C++ / 프로그래머스 / 2회 모의고사 - 신입사원 교육

문제

 

https://school.programmers.co.kr/learn/courses/15009/lessons/121688

프로그래머스

 

문제풀이

 

우선순위 큐를 사용하면 간단하게 풀린다.

문제를 읽어보면 사원 중에서 가장 작은 능력치를 가진 두 사원을 뽑아 더하고, 더한 값이 두 사원은 능력치가 된다.

따라서 우선순위 큐를 사용해서 오름차순으로 정렬을 하고, top부분의 두 원소를 뽑아 값을 더하고 다시 우선순위 큐에 입력하면 된다.

 

코드

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

int solution(vector<int> ability, int number) {
    int answer(0);
    priority_queue<int, vector<int>, greater<int>>pq_clerk;

    for (int idx = 0; idx < ability.size(); ++idx) {
        pq_clerk.push(ability[idx]);
    }

    for (int idx = 0; idx < number; ++idx) {
        int clerk_1 = pq_clerk.top();
        pq_clerk.pop();
        int clerk_2 = pq_clerk.top();
        pq_clerk.pop();
        pq_clerk.push(clerk_1 + clerk_2);
        pq_clerk.push(clerk_1 + clerk_2);
    }

    while (!pq_clerk.empty()) {
        answer += pq_clerk.top();
        pq_clerk.pop();
    }
    return answer;
}