PriorityQueue

Question

안녕하세요 선생님  강의를 보다가 문제가 잘 이해가 가지 않아서 질문드립니다. PriorityQueue 문제 내용이   양의 정수 길이의 두 막대기 연결할 수 있다. x와 y의 비용을 지불한다 스틱 x + y => 이런식으로 연결하여 스틱이 하나만 남을 때까지 모든 스틱을 최소 연결 비용을 반환합니다.   인데요... 그 다음에 나오는 예시가 스틱 = [1, 8, 3, 5] 일때 1하고 3을 갑자기 더하고  그 더해진 값인 4하고 5를 더하고 이런식으로 작은 값부터 더해가시는데요...   위의 문제 내용중에 작은값부터 x 와 y를 정하여 라는 말도없는데 갑자기 이런식으로 더해가니까 이해가 되지를 않습니다..ㅠ 전반적으로 문제들이 앞뒤가 잘려있는 느낌이 듭니다. 설명 부탁드립니다.😥

pushupman · Answer

devJR 님 안녕하세요~~ 질문주신 문제는 priorityQueue관련 문제입니다. 1. 개념설명에서 MinHeap과 MaxHeap에 대한 설명을 보시면 이문제는 MinHeap으로 만들어서 푸시는 대표적인 예제입니다.   2. 문제에 대한 정확한 이해 : 이문제는 스틱의 길이를 작은거 부터 합치고 합쳐서 total cost가 minimum이 되도록하는게 목적입니다. 그래서 1, 8,2,5에서 1+2을 선택 가장작은것들을 합치는거죠 => 가장작은것들 여기서 소팅을 하든가, 아니면 minHeap을 이용하는거죠 이문제는 Heap을 이용한 대표적인 문제입니다. 아래 그림을 보면 내부적으로 minHeap을 만들어서 자체적으로 계속 꼭대기 값은 작은 값을 유지합니다.(자바에서 디폴트는 MinHeap입니다. 작->큰거)       3. 그림