PriorityQueue(우선순위 큐) 알고리즘 파버리기

 

 

일반적으로 Queue라는 자료구조는 '선입선출'(First-In, First-Out)의 대기열 규칙(queuing discipline)을 가지고 있다.

 

하지만 JAVA에서 제공하는 'PriorityQueue'는 우선순위를 결정하여 들어온 순서와 상관없이 그 우선순위가 높은 엘리먼트가 나가게 된다.

즉 정렬이 되어 큐에 배치된다는것이다.

주의할사항은 우선순위큐에 객체만 삽입가능하다!

 

아래 예를 한번 살펴보자

 

Friend라는 클래스는  이름과 위치값을 가지고 있다.

위치값은 커질수록 멀리산다는 이야기이다.

예전에 배웠듯이 Comparable을 통해서 정렬은 한다.

+Comparable / Comparator 인터페이스가 궁금하다면 java 게시물을 찾아보기를 추천한다.

public class Friend implements Comparable<Friend> {
	String name;
	int location;
	
	public Friend(String name, int location) {
		this.name = name;
		this.location = location;
	}
	
	
	@Override
	public int compareTo(Friend bf) {
		if(this.location > bf.location) {
			return 1;
		}else if(this.location < bf.location) {
			return -1;
		}
		
		return 0;
	}

}

 

	public int solution(int[] scoville, int K) {
	        int answer = 0;
	        PriorityQueue<Friend> pq = new PriorityQueue<Friend>();
	        
	        Friend f1 = new Friend("a", 5);
	        Friend f2 = new Friend("b", 10);
	        Friend f3 = new Friend("c", 3);
	        Friend f4 = new Friend("d", 54);
	        
	        pq.offer(f1);
	        pq.offer(f2);
	        pq.offer(f3);
	        pq.offer(f4);
	        
	        System.out.println(pq.poll().location);
	        System.out.println(pq.poll().location);
	        System.out.println(pq.poll().location);
	        System.out.println(pq.poll().location);
	        
			return answer;
	        
	    }

데이터를 출력해보면 

3

5

10

54

이런식으로 출력이 되는걸 볼수있다.