[Java] 5576번. 콘테스트 (#익명 클래스)

문항출처 : https://www.acmicpc.net/problem/5576

주어진 숫자 10개에서 가장 높은 값 3개를 출력하는 문제이다. 배열에 담아 Arrays.sort를 사용하여 1,2,3위값을 구하는 것이 일반적이겠으나 만약 이 문제에서 숫자의 갯수가 많아진다면 Arrays.sort에서 시간복잡도가 NlogN이 되므로 우선순위큐를 사용하여 시간복잡도를 NlogN이 가져가는 것이 더 효율적일 것이다.

배열과 정렬을 사용하는 방법은
입력은 시간복잡도가 상수이나 출력과정에서 정렬에서 시간복잡도가 NlogN이 소요된다

우선순위큐를 사용하면 입력과 출력에서 모두 시간복잡도가 LogN이므로 우선순위큐가 더 유리하다.

기본적으로 큐는 선입선출이고 우선순위큐는 다른 옵션을 정하지 않으면
오름차순 정렬이기 때문에 poll을 통해서 값을 꺼낼 때 최소값 3개가 나오게 되므로
내림차순으로 우선순위큐가 작동하도록 수정할 필요가 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

class Main {
    static PriorityQueue<Integer> pq;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {

        int W = getScore();
        int K = getScore();
        System.out.println(W+" "+K);
    }

    static int getScore() throws IOException {
        int answer = 0;
        //우선순위 큐 선언
        pq = new PriorityQueue<>(new Comparator<Integer>() {
        	//익명 클래스 new Comparator를 선언하고 크기비교 로직을
            //오버라이드로 재정의해준다.
            //return이 음수이면 o1이 앞으로, 양수이면 o2가 앞으로 온다.
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for(int i = 1 ; i <= 10 ; i++){
            pq.add(Integer.parseInt(br.readLine()));
        }
        for(int i = 1 ; i <= 3 ; i++){
            answer += pq.poll();
        }
        return answer;
    }
}