[해커랭크(HackerRank) JAVA 풀이] - Java Priority Queue

해커랭크 - https://www.hackerrank.com/
Prepare > Java > Data Structures > Java Priority Queue

HackerRank

 

컴퓨터 과학에서 우선순위 대기열은 일반 대기열과 비슷하지만 추가로 각 요소에 연결된 "우선순위"가 있는 추상 데이터 유형입니다. 우선순위 대기열에서 우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 제공됩니다. - 위키피디아

 

학교에는 봉사를 기다리는 많은 학생들이 있습니다. ENTER 및 SERVED의 두 가지 유형의 이벤트가 발생할 수 있으며 아래에 설명되어 있습니다.

• ENTER : 어떤 우선 순위를 가진 학생이 서비스를 받기 위해 대기열에 들어갑니다.
• SERVED : 우선 순위가 가장 높은 학생이 대기열에서 서비스(제거)됩니다.

 

대기열에 입장하는 각 학생에게는 고유한 ID가 할당됩니다. 대기열은 다음 기준(우선순위 기준)에 따라 학생에게 서비스를 제공합니다.

1. 누적 학점 평균(CGPA)이 가장 높은 학생이 먼저 제공됩니다.
2. 동일한 CGPA를 가진 모든 학생은 대소문자를 구분하는 알파벳 오름차순으로 이름이 제공됩니다.
3. 동일한 CGPA 및 이름을 가진 모든 학생은 ID의 오름차순으로 제공됩니다.

 

다음 두 클래스를 만듭니다.

• 학생 클래스는 다음을 구현해야 합니다.
  ο 생성자 Student(int id, String name, double cgpa).
  ο int getID() 메소드는 학생의 ID를 반환합니다.
  ο String getName() 메서드는 학생의 이름을 반환합니다.
  ο 메소드는 학생의 CGPA를 반환하기 위해 getCGPA()를 더블로 합니다.
• Priorities 클래스는 List<Student> getStudents(List<String> events) 메서드를 구현하여 주어진 모든 이벤트를 처리하고 우선순위에 따라 아직 처리되지 않은 모든 학생을 반환해야 합니다.

 

Input Format

첫 번째 줄에는 총 이벤트 수를 설명하는 정수 n이 있습니다. n개의 후속 라인 각각은 다음 두 가지 형식이 됩니다.

• ENTER name CGPA id : 우선 순위 대기열에 삽입할 학생입니다.
• SERVED : 대기열에서 가장 높은 우선 순위의 학생이 서비스를 받았습니다.

편집기의 잠긴 스텁 코드는 입력을 읽고 Student 및 Priorities 클래스 구현의 정확성을 테스트합니다.

 

Constraints

• 2 ≤ n ≤ 1000
• 0 ≤ CGPA ≤ 4.00
• 1 ≤ id ≤ 10⁵
• 2 ≤ |name| ≤ 30

 

Output Format

잠긴 스텁 코드는 우선 순위에 따라 아직 제공되지 않은 학생의 이름을 인쇄합니다. 그러한 학생이 없으면 코드는 EMPTY를 인쇄합니다.

 

 

Sample Input

12
ENTER John 3.75 50
ENTER Mark 3.8 24
ENTER Shafaet 3.7 35
SERVED
SERVED
ENTER Samiha 3.85 36
SERVED
ENTER Ashley 3.9 42
ENTER Maria 3.6 46
ENTER Anik 3.95 49
ENTER Dan 3.95 50
SERVED

 

Sample Output

Dan
Ashley
Shafaet
Maria

 

Explanation

이 경우 이벤트의 개수는 12개입니다. 큐의 이름을 Q라고 합니다.

• John이 Q에 추가되었습니다. 따라서 여기에는 (John, 3.75, 50)이 포함됩니다.
• Q에 Mark가 추가되었습니다. 따라서 (John, 3.75, 50) 및 (Mark, 3.8, 24)가 포함됩니다.
• Q에 Shafaet이 추가되었습니다. 따라서 (John, 3.75, 50), (Mark, 3.8, 24) 및 (Shafaet, 3.7, 35)가 포함됩니다.
• Mark는 CGPA가 가장 높기 때문에 제공됩니다. 따라서 Q에는 (John, 3.75, 50) 및 (Shafaet, 3.7, 35)가 포함됩니다.
• John은 CGPA가 가장 높기 때문에 다음으로 봉사합니다. 따라서 Q에는 (Shafaet, 3.7, 35)가 포함됩니다.
• Samiha가 Q에 추가되었습니다. 따라서 (Shafaet, 3.7, 35) 및 (Samiha, 3.85, 36)이 포함됩니다.
• Samiha는 그녀가 가장 높은 CGPA를 가지고 있기 때문에 제공됩니다. 따라서 Q에는 (Shafaet, 3.7, 35)가 포함됩니다.
• 이제 4명의 학생이 Q에 추가되었습니다. 따라서 (Shafaet, 3.7, 35), (Ashley, 3.9, 42), (Maria, 3.6, 46), (Anik, 3.95, 49) 및 (Dan, 3.95, 50).
• Anik은 Anil과 Dan 모두 CGPA가 가장 높지만 알파벳 순서로 정렬할 때 Anik이 먼저 오기 때문에 제공됩니다. 따라서 Q에는 (Dan, 3.95, 50), (Ashley, 3.9, 42), (Shafaet, 3.7, 35) 및 (Maria, 3.6, 46)이 포함됩니다.

모든 이벤트가 완료되면 나머지 학생의 이름이 새 줄에 출력됩니다.

 

 

Code

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*
 * Create the Student and Priorities classes here.
 */
class Student {
    private int id;
    private String name;
    private 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;
    }
}

class Priorities {
    public List<Student> getStudents(List<String> events) {
        List<Student> students = new ArrayList<>();

        for (String event : events) {
            String[] parts = event.split(" ");
            if (parts[0].equals("ENTER")) {
                String name = parts[1];
                double cgpa = Double.parseDouble(parts[2]);
                int id = Integer.parseInt(parts[3]);
                Student student = new Student(id, name, cgpa);
                students.add(student);
            } else if (parts[0].equals("SERVED")) {
                if (!students.isEmpty()) {
                    students.sort((s1, s2) -> {
                        if (s1.getCGPA() != s2.getCGPA()) {
                            return Double.compare(s2.getCGPA(), s1.getCGPA());
                        } else if (!s1.getName().equals(s2.getName())) {
                            return s1.getName().compareTo(s2.getName());
                        } else {
                            return Integer.compare(s1.getID(), s2.getID());
                        }
                    });
                    students.remove(0);
                }
            }
        }

        return students;
    }
}


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<String> events = new ArrayList<>();
        
        while (totalEvents-- != 0) {
            String event = scan.nextLine();
            events.add(event);
        }
        
        List<Student> students = priorities.getStudents(events);
        
        if (students.isEmpty()) {
            System.out.println("EMPTY");
        } else {
            for (Student st: students) {
                System.out.println(st.getName());
            }
        }
    }
}

 

 

 

개인 공부를 위한 포스팅입니다.
모든 번역, 코드는 완벽하지 않을 수 있습니다.