[프로그래머스] 42626 더 맵게

프로그래머스 level2

문제

문제 풀이

문제 리뷰

이 문제는 힙 카테고리에 속해있는 문제이다.
그래서 힙정렬을 활용한 우선순위 큐를 사용하여 푸는 문제이다.
나는 우선순위 큐를 다뤄본 적이 없어서 개념을 공부한 후, 풀었다.

힙 (Heap)

• 완전 이진 트리
  
• 데이터에서 최대값 or 최소값을 빠르게 찾을 수 있는 정렬
  
• 우선순위가 가장 높은 데이터가 제일 앞(루트)에 위치한다.
  

• 최대힙(Max Heap) / 최소힙(Min Heap)
  

  최대힙 - 데이터 중 가장 큰 값이 루트에 위치 (내림차순 / 5,4,3..)
  

  최소힙 - 데이터 중 가장 작은 값이 루트에 위치 (오름차순 / 1,2,3..)
  

---

큐 (Queue) : 선입선출

먼저 들어온게 먼저 나감

우선순위 큐 (Priority Queue)

• 우선순위를 결정하여 들어온 순서와 상관 없이
  우선 순위가 높은 데이터가 나간다.
  

• 기본적으로는 우선순위가 최소힙(오름차순)을 따른다.
  

  최대힙(내림차순)으로 구현하고 싶다면 큐를 reverse 정렬을 해줘야한다.
  

✅ 우선순위 큐 메소드 정리

✔︎ 삽입

pq.offer(Object o)

pq.add(Object o)

✔︎ 제거

제거는 항상 앞(front)에서 발생한다.

pq.poll()

• 큐가 비어있다면 null을 반환

pq.remove()

• 큐가 비어있다면 예외 발생

✔︎ 읽기

큐에서 앞(front) 데이터를 읽는 작업

pq.peek()

• 큐가 비어있다면 null을 반환

pq.element()

• 큐가 비어있다면 예외 발생

TMI

하나 배워갑니다.

1일 1알고리즘 완료🤓

참고

• 우선순위 큐 & 힙(Priority Queue & Heap)
• [JAVA] 우선순위(PriorityQueue) 큐
• 자바 :: Priority Queue?