2019년 7월 24일 수요일

Java Priority Queue (우선순위큐)




* Priority Queue, 우선순위 큐

우선순위큐는 말 그대로 큐의 성질을 가졌으나, 각 데이터가 우선순위를 갖고 있어 우선순위가 높은 순서대로 나오게 된다. 
 만약 우선순위가 동일하다면 큐에서 그들의 순서에 의해 처리된다.
 아래 문제는 이미 구현되어져 있는 자바 클래스인 PriorityQueue를 가지고 원하는 우선순위를 구현할 수 있는지에 대한 문제이다. 
 어떤 객체의 내부속성에 대해 특별한 기준으로 정렬을 하고 싶다면 Comparable 인터페이스의 compareTo 메소드를 구현하면 된다.
 아래 Student 클래스의 예시에서 우선순위대로 정렬의 기준을 구현하였다.
CGPA 점수가 높은 것이 우선순위가 더 높다고 하였으므로,비교대상점수가 더 높을 경우 원래라면 -1을 리턴하여 앞이 더 앞서다고 나타내야겠지만 1을 return 함으로써 그 순서가 역(내림차순)으로 정렬을 해야한다는 점을 알려준다.
이 부분이 이해가 되지 않을 경우 예전 게시글을 참고한다.

* 참고 : compareTo

compareTo 메소드는 매번 헷갈리는 부분이 있어 문제에 등장할 때마다 정리하게 된다.😓

결론은 정렬 기준의 순서대로 PriorityQueue에서 poll() 하는 경우 우선순위가 높은 것부터 나오게 된다.  




import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.*;
/*
 * Create the Student and Priorities classes here.
 */
class Student implements Comparable{
    int id;
    String name;
    double cgpa;

    public Student(int id, String name, double cgpa){
        this.id = id;
        this.name = name;
        this.cgpa = cgpa;
    }
    public int getID(){
        return id;
    }
    public String getName(){
        return name;
    }
    public double getCGPA(){
        return cgpa;
    }
    @Override
    public int compareTo(Student target){
        if(this.cgpa < target.getCGPA()){
            return 1;
        }else if(this.cgpa == target.getCGPA()){
            if( this.name.compareTo(target.getName()) < 0) { //String의 비교는 String에 내장된 것을 사용.
                return -1; //이름은 오름차순으로 정렬
            }else if( this.name.compareTo(target.getName()) == 0 ){
                if(this.id < target.getID()){
                    return -1;
                }else if(this.id == target.getID()){
                    return 0;
                }else{
                    return 1;
                }

            }else{
                return 1;
            }
        
        }else{
            return -1;
        }
    }

}

class Priorities{
    PriorityQueue q;

    List getStudents(List events){
        q = new PriorityQueue();
        List list = new ArrayList();
        //System.out.println(events.size());

        for(int i = 0 ; i < events.size();i++){
            String event = events.get(i);
            String[] eArr = event.split(" ");
            if(eArr[0].equals("SERVED")){
                q.poll();

            }else{
                q.offer(new Student(Integer.parseInt(eArr[3]),eArr[1],Double.parseDouble(eArr[2])));
            }
        }
            
        while(q.size()>0){
            list.add(q.poll());
        }
    
        return list; 
    }

}

public class Solution {
    private final static Scanner scan = new Scanner(System.in);
    private final static Priorities priorities = new Priorities();
    
    public static void main(String[] args) {
        int totalEvents = Integer.parseInt(scan.nextLine());    
        List events = new ArrayList<>();
        
        while (totalEvents-- != 0) {
            String event = scan.nextLine();
            events.add(event);
        }
        
        List students = priorities.getStudents(events);
        
        if (students.isEmpty()) {
            System.out.println("EMPTY");
        } else {
            for (Student st: students) {
                System.out.println(st.getName());
            }
        }
    }
}

댓글 없음:

댓글 쓰기