[BOJ] 후보 추천하기

[1713] 후보 추천하기

www.acmicpc.net/problem/1713

 

 

Solution

• 문제에서 주어진 조건대로 구현하면 되는 문제
• idx, like, order 속성을 가진 Student 객체를 만들어 추천받은 순서 대로 우선순위 큐에 넣었다.
• 우선순위 큐의 정렬 조건은 like, 추천수가 작은 Student가 먼저 빠져나오고 추천수가 같은 경우에는 order, 들어간 순서가 오래된 Student가 먼저 나오도록 했다.
• 추천받을 학생이 이미 우선순위 큐에 들어있는 경우에는 해당 학생은 like, 추천수를 업데이트 한 후 다시 넣어줬다.
• 우선순위 큐에 들어있는 Student를 뽑지 않고 큐 들어있는 상태에서 like를 업데이트 하면 큐의 정렬 조건에 반영되지 않으므로 모든 Student 객체를 뽑은 후에 다시 넣어주었다.
• 왜 그런지는 모르겠네,, 

 

 

소스코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;
 
public class Main {
    static int n, m;
 
    static class Student implements Comparable<Student> {
        private int num, like, order;
 
        public Student(int num, int like, int order) {
            this.num = num;
            this.like = like;
            this.order = order;
        }
 
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Student student = (Student) o;
            return num == student.num;
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(num);
        }
 
        @Override
        public int compareTo(Student o) {
            if (this.like == o.like) {
                return this.order - o.order;
            } else {
                return this.like - o.like;
            }
        }
 
        @Override
        public String toString() {
            return "Student [num=" + num + ", like=" + like + ", order=" + order + "]";
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = stoi(in.readLine());
        int m = stoi(in.readLine());
 
        StringTokenizer st = new StringTokenizer(in.readLine());
        PriorityQueue<Student> pq = new PriorityQueue<>();
        int order = 1;
        while (st.hasMoreTokens()) {
            int num = stoi(st.nextToken());
            if (pq.contains(new Student(num, 0, 0))) {
                Student[] temp = new Student[pq.size()];
                for (int i = 0; i < temp.length; i++) {
                    temp[i] = pq.poll();
                }
                pq.clear();
                for (Student s : temp) {
                    if (s.num == num) {
                        s.like++;
                    }
                    pq.offer(s);
                }
            } else if (pq.size() >= n) {
                pq.poll();
                pq.offer(new Student(num, 1, order++));
            } else {
                pq.offer(new Student(num, 1, order++));
            }
        }
 
        Student[] result = new Student[n];
        int idx = 0;
        while (!pq.isEmpty()) {
            result[idx++] = pq.poll();
        }
        Arrays.sort(result, new Comparator<Student>() {
 
            @Override
            public int compare(Student s1, Student s2) {
                return s1.num - s2.num;
            }
        });
        StringBuilder sb = new StringBuilder();
        for (Student s : result) {
            sb.append(s.num + " ");
        }
        System.out.println(sb.toString().trim());
 
    }
 
    static int stoi(String s) {
        return Integer.parseInt(s);
    }
}