[Java]PriorityQueue

프로그래머스 코딩테스트 연습문제를 진행하다가..

Heap 자료구조와 관련된 문제를 ArrayList로 풀었다가 효율성에서 완벽하게 실패했다.

 

역시 문제에서 제시하듯이 Heap 자료구조에 대한 공부와 함께 해당하는 라이브러리를 사용해야 할 것 같았다.

 

그리고 프로그래머스 질문하기에서 누군가 Heap에 대해 상세하게 설명한 링크를 띄워주었다.

(https://shanepark.tistory.com/261)

 

Heap 자료구조는 최소, 최대값을 가져오는데에 최적화 된 자료 구조이고, 루트값만 가져오면 되기 때문에, 시간복잡도 또한 O(1)이다.

그리고 새로운 값을 추가(add) 또는 삭제(poll)할 경우의 시간복잡도는 O(log n)이다.

 

해당링크로 들어가 Heap 구조에 대해 이해하고 이러한 구조를 구현한 라이브러리가 PriorityQueue 인 것을 알게되었다.

 

선언

값 추가

우선순위가 가장 높은 값 반환

우선순위가 가장 높은 값을 반환하면서 삭제

단순 삭제는 remove() 메서드를 통해 가능하다.

 

* 코딩테스트를 한문제씩 연습하다보면 다양한 자료구조에 대한 이해를 요구하는 경우가 많다. 기본자료형과 몇몇 컬렉션 위주로만 숙지하고 있다보니, 이러한 케이스에서 효율성 문제를 계속 만나는 것 같다.