[PCCP모의고사2] 2번 신입사원 교육 JAVA

문제 (우선순위 큐)

 

프로그래머스

 

 

문제 풀이

 

처음에는 Arrays.sort() 사용하여 매번 반복해서 정렬 후 앞 2개를 뽑아내서 더해줬었다.

시간초과 날 것 같긴했는데 역시나..ㅎ 제일 작은 수를 뽑아내기 위해 정렬말고 다른 자료 구조를 써야 효과적으로 뽑아낼 수 있을까 고민했는데 결국에는 구글링을 통해 Priority Queue(우선순위큐) 를 이용해야 한다는 것을 알게 되었다.

우선순위큐 자체는 자바에 내장되어 있는 자료구조를 바로 이용하면 되서 구현은 참 쉬웠지만 내부적인 원리를 이해하려면 조금 각잡고 트리 공부를 해야할 것 같았다.

 

참고 사이트:https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90

https://devkingdom.tistory.com/226

[JAVA] JAVA 메모리 이야기 - Stack 과 Heap

[Java] Priority Queue(우선 순위 큐)

 

 

소스 코드

 

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] ability, int number) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
		int ans = 0;
		
		for(int a : ability)
			pq.add(a);
		
		for(int i = 0; i < number; i++) {
			int sum = pq.poll();
			sum += pq.poll();
			pq.add(sum);
			pq.add(sum);
		}
		
		for(int i = 0; i < ability.length; i++)
			ans += pq.poll();

        return ans;
    }
}