Priority Queue

오늘은 프로그래머스 힙부분 Level2 문제인 "더 맵게 " 문제를 진행했다.

 

문제는 생각했던것 보다 쉽게 풀렸고 테스트케이스를 순조롭게 통과하였고 채점 및 제출 버튼을 눌렀다.

 

하지만 예상치못한 17점이라는 점수와 실패라는 결과를 받았고 컴파일 에러와 효율성 점수에서 문제를 확인 할 수 있었다.

 

다른 분들의 코드를 확인 해 본 결과 이 문제는 Priority Queue 즉 우선순쉬 큐를 활용해야 효율성 테스트에서 통과 할 수 있었다. ( 합격자들 코드 전부 우선순위큐를 사용함)  < 우선순위큐는 힙으로 구현되어있음>

 

우선순위큐는 크기에 상관없이 막 넣어도 peek 나 remove를 통해서 내부적으로 정렬된 가장 작은 값을 반환해준다.

이 점을 활용해서 우선순위큐는 Sort메소드를 활용할 필요가 없어져 낭비되는 시간을 줄일 수 있었다.

 

우선순위큐는 내부적으로 Natural Ordering 기법( 숫자는 1, 알파벳은 a부터) 에 따라 정렬해준다.

 

Priority 큐 라이브러리를 사용하기 위해서는 우선 java.util.PriorityQueue 를 임포트 해야하고

 

PriorityQueue<Integer> pq = new PriorityQueue<>(); 와 같이 선언하면 된다.

 

기본은 낮은 숫자가 우선순위를 부여받지만 만약 높은 숫자로 우선순위를 부여하고 싶다면 Collections.reverseOrder() 메소드를 활용할 수 있다.

 

미리 약속해서 정렬 기준 정해놓기 --> Comparable 인터페이스 구현

 

PriorityQueue()   : 원소들의 natural ordering에 따라 Heap유지, 따라서 반드시 모든 원소는 Comparable 인터페이스를 구현해야함.

 

PriorityQueue(Comparator comparator)    : 명시된 comparator의 구현에 따라 원소들의 순서를 유지   

 

 

Priroty Queue 값 추가 : pq.add(value);    //offer 

 

Priroty Queue 값 삭제와 동시에 반환가능 : pq.remove();      //poll 

 

Priroty Queue 에 우선순위가 가장 높은 값 출력 : pq.peek();