[백준] 3758: KCPC - JAVA

20 Sep 2023 in Algorithm on 정렬

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

풀이

내 팀이 몇 등인지 구하는 문제이다.

점수가 동일한 팀이 있는 경우 다음 규칙에 따라 정해진다.

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다.

2. 최종 점수도 같고, 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.

이 규칙들을 우선순위큐에 적용하여 점수, 횟수, 제출시간을 class에 넣고

우선순위큐에서 뽑으면서 rank를 메겼다.

---

메모리: 34920KB

시간: 356ms

언어: Java 11

코드

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

public class Main {

    static class Node implements Comparable<Node> {
        int cnt;
        int total;
        int time;
        boolean myTeam;

        public Node(int cnt, int total, int time, boolean myTeam) {
            this.cnt = cnt;
            this.total = total;
            this.time = time;
            this.myTeam = myTeam;
        }

        @Override
        public int compareTo(Node o) {
            if (this.total == o.total) {
                if (this.cnt == o.cnt) {
                    return Integer.compare(this.time, o.time);
                }
                return Integer.compare(this.cnt, o.cnt);
            }
            return Integer.compare(o.total, this.total);
        }

    }

    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++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            int[] count = new int[n + 1];
            int[][] score = new int[n + 1][k + 1];
            int[] time = new int[n + 1];
            for (int i = 0; i < m; i++) {
                st = new StringTokenizer(br.readLine());
                int id = Integer.parseInt(st.nextToken());
                int num = Integer.parseInt(st.nextToken());
                int s = Integer.parseInt(st.nextToken());

                count[id]++;
                score[id][num] = Math.max(s, score[id][num]);
                time[id] = i;
            }

            PriorityQueue<Node> pq = new PriorityQueue<>();
            for (int i = 1; i < n + 1; i++) {
                int sum = 0;
                for (int j = 1; j < k + 1; j++) {
                    sum += score[i][j];
                }
                pq.add(new Node(count[i], sum, time[i], i == t ? true : false));
            }

            int rank = 0;
            while (!pq.isEmpty()) {
                Node node = pq.poll();
                rank++;
                if (node.myTeam) {
                    break;
                }
            }

            sb.append(rank).append("\n");
        }

        System.out.println(sb);
    }

}