인프런 커뮤니티 질문&답변
작성한 질문수
PriorityQueue
해결된 질문
작성
·
233
1
안녕하세요 선생님
강의를 보다가 문제가 잘 이해가 가지 않아서 질문드립니다.
PriorityQueue 문제 내용이
양의 정수 길이의 두 막대기 연결할 수 있다.
x와 y의 비용을 지불한다 스틱 x + y =>
이런식으로 연결하여 스틱이 하나만 남을 때까지 모든 스틱을
최소 연결 비용을 반환합니다.
인데요...
그 다음에 나오는 예시가
스틱 = [1, 8, 3, 5]
일때 1하고 3을 갑자기 더하고
그 더해진 값인 4하고 5를 더하고
이런식으로 작은 값부터 더해가시는데요...
위의 문제 내용중에 작은값부터 x 와 y를 정하여 라는 말도없는데 갑자기 이런식으로 더해가니까 이해가 되지를 않습니다..ㅠ
전반적으로 문제들이 앞뒤가 잘려있는 느낌이 듭니다.
설명 부탁드립니다.😥
답변 1
1
devJR 님 안녕하세요~~
질문주신 문제는 priorityQueue관련 문제입니다.
1. 개념설명에서 MinHeap과 MaxHeap에 대한 설명을 보시면 이문제는 MinHeap으로 만들어서 푸시는 대표적인 예제입니다.
2. 문제에 대한 정확한 이해 :
이문제는 스틱의 길이를 작은거 부터 합치고 합쳐서 total cost가 minimum이 되도록하는게 목적입니다.
그래서 1, 8,2,5에서
1+2을 선택 가장작은것들을 합치는거죠 => 가장작은것들 여기서 소팅을 하든가, 아니면 minHeap을 이용하는거죠 이문제는 Heap을 이용한 대표적인 문제입니다. 아래 그림을 보면 내부적으로 minHeap을 만들어서 자체적으로 계속 꼭대기 값은 작은 값을 유지합니다.(자바에서 디폴트는 MinHeap입니다. 작->큰거)
3. 그림
