[PCCP 모의고사 2회] 2번 신입사원 교육 - 자바(java)

 

문제 이해

신입 사원 2명이 각각  a와 b 능력치가 있을 때

민수가 가르친다면 a+b , a+b 능력치가 된다

 

-> 이 때 최소가 되는 값을 구하라

 

알고리즘

Greedy로 쉽게 풀 수 있을 것 같아서 PriorityQueue를 이용해서 풀 생각을 하였다.

Greedy가 의심될 때 가장 주의해야 할 것은 예외가 생길 수 있냐는 것이다.

 

전체 값이 최소가 되기 위해서는 신입 사원들 중 능력치가 제일 낮은 2명을 뽑아야하는 것이 맞으므로

Greedy로 풀 수 있다는 것을 확정지었다.

 

1. ability를 전부 PQ에 넣어놓고 제일 낮은 값 2명을 뽑으면 되니까 람다식 없이 기본 pq를 사용함
2. number을 하나씩 갈 때 마다 pq에서 2명 뽑고 그 둘을 더한 값을 다시 pq에 두번 집어넣는 것을 반복
3. number가 끝났다면 pq를 비울 때까지 돌면서 answer에 더해줌

코드

import java.util.*;
class Solution {
    public int solution(int[] ability, int number) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int a : ability){
            pq.add(a);
        }
        for(int i = 0; i < number; i++){
            int a = pq.poll();
            int b = pq.poll();
            int newAbil = a+b;
            pq.add(newAbil);
            pq.add(newAbil);
        }
        while(!pq.isEmpty()){
            answer+=pq.poll();
        }
        return answer;
    }
}