7662번 - 이중 우선순위 큐
c언어로 문제를 풀어보려합니다. 맥스힙과 민힙을 짜서 인서트 할때마다 두개의 힙에 값을 넣고 값을 뺄대 맥스힙에서 뺀다면
민힙에서는 그 값을 찾아서 삭제시켜야하는데 그 값을 탐색해서 찾을 수 있나? 라는 생각이들었습니다. 모든 값을 뒤지면 찾을 수 있겠지만
시간이 오래 걸릴 것 같습니다. 구글링 언어는 다 java풀이라 이해가 안돼서 질문 드립니다. 코드는 아직 안짜봐서 올리지 않았습니다. 힙자체는 구현 할 수 있지만 딜리트 부분 구현을 어떻게 해야할지 감이 잡히지 않아 질문드립니다.
배열로 힙을 만들어 구현하신다면, 그 방법으로 푸는것이 가능합니다. 최댓값을 제거하는 경우 민힙에서 그값을 찾아야하는데, 힙의 구조상 가장 큰값은 트리로 따지면 리프쪽에 있겠죠. 그부분은 완탐으로 찾아서 값을 삭제해나가도 돌아가긴 합니다.
댓글 감사드립니다. 시간초과가 나올것 같아서 구현해보지 않았는데 한번 해보겠습니다.
댓글을 작성하려면 로그인해야 합니다.
akqjqcjs7 3년 전
c언어로 문제를 풀어보려합니다. 맥스힙과 민힙을 짜서 인서트 할때마다 두개의 힙에 값을 넣고 값을 뺄대 맥스힙에서 뺀다면
민힙에서는 그 값을 찾아서 삭제시켜야하는데 그 값을 탐색해서 찾을 수 있나? 라는 생각이들었습니다. 모든 값을 뒤지면 찾을 수 있겠지만
시간이 오래 걸릴 것 같습니다. 구글링 언어는 다 java풀이라 이해가 안돼서 질문 드립니다. 코드는 아직 안짜봐서 올리지 않았습니다. 힙자체는 구현 할 수 있지만 딜리트 부분 구현을 어떻게 해야할지 감이 잡히지 않아 질문드립니다.