우선순위 큐 : 백준 11279번 1927번 java

우선순위 큐 (Priority Queue)

일반적인 큐는 제일 먼저 들어간 데이터가 가장 먼저 나오게 되는 FIFO 자료 구조

우선순위 큐는 들어간 순서에 상관없이 일정한 규칙에 따라 우선순위를 선정하고, 우선순위가 가장 높은 데이터가 가장 먼저 나오게 됨.

 

사용하기

java에 내부적으로 구현되어 있다. 일반적인 큐처럼 add(); peek(); poll(); 등의 메소드를 사용할 수 있다.

 

PriorityQueue<Integer> pq = new PriorityQueue<>();

pq.add(4); //offer(); 메소드를 사용해도 동일하게 추가됩니다.
pq.add(3);
pq.add(2);
pq.add(1);

Integer poll = pq.poll();
System.out.println(poll); //출력결과 1

일반적인 큐와 다르게 가장 먼저 들어간 4가 아니라, 우선순위가 높은 1이 가장 먼저 들어감. 기본적으로는 낮은 숫자가 우선순위가 높습니다.

 

우선순위 변경하기

우선순위를 정하는 기준은 Java의 정렬 기준과 동일

Java는 기본적으로 낮은 숫자부터 큰 숫자로 오름차순으로 정렬하게 되는데, 다른 오름차순을 사용하고 싶다면 Comparator 클래스나 Comparable 인터페이스를 이용해야 한다.

Integer와 같은 숫자는 Collections.reverseOrder()를 사용하면 간편하게 우선순위를 변경할 수 있다.

//우선순위를 내림차순으로 변경
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

 

 

 

백준 11279번 문제

jeon9825/TIP

백준 1927번 문제

jeon9825/TIP

처음엔 백준 12279번과 1927번을 int 배열과 ArrayList<Integer>로 풀었는데 시간초과가 떴다. 문제가 있는 것 같아서 찾아보다가 우선순위 큐로 풀어야한다는 것을 배웠다. 우선순위 큐 말고 다른 방식으로 풀면 왜 시간초과가 뜨는지는 잘 모르겠다. 단순 java가 시간을 많이 잡아먹는게 문제인가