프로그래머스 코딩테스트 연습문제를 진행하다가..
Heap 자료구조와 관련된 문제를 ArrayList로 풀었다가 효율성에서 완벽하게 실패했다.
역시 문제에서 제시하듯이 Heap 자료구조에 대한 공부와 함께 해당하는 라이브러리를 사용해야 할 것 같았다.
그리고 프로그래머스 질문하기에서 누군가 Heap에 대해 상세하게 설명한 링크를 띄워주었다.
(https://shanepark.tistory.com/261)
Heap 자료구조는 최소, 최대값을 가져오는데에 최적화 된 자료 구조이고, 루트값만 가져오면 되기 때문에, 시간복잡도 또한 O(1)이다.
그리고 새로운 값을 추가(add) 또는 삭제(poll)할 경우의 시간복잡도는 O(log n)이다.
해당링크로 들어가 Heap 구조에 대해 이해하고 이러한 구조를 구현한 라이브러리가 PriorityQueue 인 것을 알게되었다.
선언
값 추가
우선순위가 가장 높은 값 반환
우선순위가 가장 높은 값을 반환하면서 삭제
단순 삭제는 remove() 메서드를 통해 가능하다.
* 코딩테스트를 한문제씩 연습하다보면 다양한 자료구조에 대한 이해를 요구하는 경우가 많다. 기본자료형과 몇몇 컬렉션 위주로만 숙지하고 있다보니, 이러한 케이스에서 효율성 문제를 계속 만나는 것 같다.
'개발 > Java' 카테고리의 다른 글
[Algorithm]구간합 구하기 (0) | 2022.04.24 |
---|---|
[Java]Comparator (0) | 2022.03.31 |
[Java]Call by value, Call by reference (0) | 2022.03.09 |
[Java]순수 자바 코드로 DIP와 OCP를 준수하는 방법 (0) | 2022.03.06 |
[CS]객체 지향 설계의 5원칙(SOLID) (0) | 2022.03.02 |