[Programmers] PCCP 모의고사 2회 2번 - 신입사원 교육 - Java

문제

프로그래머스

 

풀이

교육받은 사원의 능력치의 합이 사원의 능력치가 되는데, 능력치의 합을 최소화 시켜야하는 문제이다.

그러면, 능력치가 낮은 사원을 계속 꺼내서 더하면 능력치의 합이 최소화 될 것이라는 생각이 든다.

 

데이터가 100만개이고, 능력치가 낮은 사원을 바로 찾아야한다 => 우선순위 큐를 사용해야할 것 같다는 생각이 든다.

log연산으로 가장 능력치 수치가 낮은 사원을 찾을 수 있기 때문이다.

 

1. 사원의 능력치를 우선순위 큐에 넣는다.

 

2. number만큼 반복문을 수행하면서, 가장 낮은 능력치를 가진 사원 둘을 뽑아서 더한 값을 다시 2번 넣어준다.

 

3. 우선순위 큐에 들어가 있는 능력치들을 더해준다.

 

소스코드 

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] ability, int number) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int a : ability) {
            pq.add(a);
        }
        
        while (number > 0) {
            int staff1 = pq.remove();
            int staff2 = pq.remove();
            
            pq.add(staff1 + staff2);
            pq.add(staff1 + staff2);
            
            number--;
        }
        
        int answer = 0;
        
        while (!pq.isEmpty()) {
            answer += pq.remove();
        }
        
        return answer;
    }
}

 

실행결과