[백준] 9017: 크로스 컨트리 - JAVA

in Algorithm on 구현

https://www.acmicpc.net/problem/9017

풀이

6명이 참여한 팀만 점수가 들어가며, 팀 당 상위 네명의 주자 합이 팀의 점수가 된다.

팀의 점수가 같을 경우 다섯번째 선수의 점수가 우승을 결정한다.

우선순위큐를 써야겠다고 생각이 들었다.

입력을 받으면서 팀 당 몇명인지 카운트를 해주었고, 6명인팀만 점수 계산을 하여 우선순위큐에 넣었다.

우선순위큐의 정렬 기준을 문제에 나와있는대로 적용했기때문에

우선순위큐에서 poll 하여 출력하면 된다.

메모리: 16448KB

시간: 184ms

언어: Java 11

코드

import java.util.*;
import java.io.*;

public class Main {

    static class Team implements Comparable<Team> {
        int no;
        int score;
        int[] records;

        public Team(int no, int score, int[] records) {
            this.no = no;
            this.score = score;
            this.records = records;
        }

        @Override
        public int compareTo(Team o) {
            if (this.score == o.score) {
                return Integer.compare(this.records[4], o.records[4]);
            }
            return Integer.compare(this.score, o.score);
        }
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 0; tc < T; tc++) {
            int N = Integer.parseInt(br.readLine());

            int[] arr = new int[N];
            int[] count = new int[201];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
                count[arr[i]]++;
            }

            ArrayList<ArrayList<Integer>> list = new ArrayList<>();
            for (int i = 0; i <= 201; i++) {
                list.add(new ArrayList<>());
            }
            int score = 1;
            for (int i = 0; i < N; i++) {
                if (count[arr[i]] == 6) {
                    list.get(arr[i]).add(score++);
                }
            }

            PriorityQueue<Team> pq = new PriorityQueue<>();
            for (int i = 0; i < 201; i++) {
                if (!list.get(i).isEmpty()) {
                    int[] tmp = new int[6];
                    for (int j = 0; j < 6; j++) {
                        tmp[j] = list.get(i).get(j);
                    }
                    Arrays.sort(tmp);
                    int sum = 0;
                    for (int j = 0; j < 4; j++) {
                        sum += tmp[j];
                    }
                    pq.add(new Team(i, sum, tmp));
                }
            }

            sb.append(pq.poll().no).append("\n");
        }

        System.out.println(sb);
    }

}