1167. Minimum Cost to Connect Sticks

문제

풀이

class Solution {
	public int connectSticks(int[] sticks) {
    
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    int cost = 0;
    
    for(int n : sticks) {
    	heap.add(n);
    }
    
    while(heap.size() > 1) {
    	int x = heap.poll();
        int y = heap.poll();
        cost += x+y;
        heap.add(x+y);
    }
    
    return cost;
    
	}
}

• stick이 하나 남을 때 까지 연산을 반복
• cost가 최소인 연산만을 수행해야 문제의 조건을 만족할 수 잇다.
  • cost가 최소이려면, 배열에서 가장 적은 길이의 stick 두 개를 뽑아서 합쳐야함
    => heap을 이용해서 최소 길이 stick 두 개 빼줘서 연산!