3758번 : KCPC

문제 출처는 여기!

정렬에 관한 문제다.

일단 어떤 데이터를 어떻게 사용할지 명확히 정해서 풀면 된다.

일단 사용할 데이터를 정한다.

t : 테스트 데이터 수
n : 팀의 개수
k : 문제 개수
id : 내 팀의 아이디
m : 로그 개수

a : 팀 아이디
b : 문제 번호
c : 획득한 점수

이렇게 주어지는 데이터들 중에서 팀의 순위를 결정하는 데에는 팀별 문제별 점수와 팀별 제출 횟수, 그리고 팀별 마지막 제출 시간이 필요하다.

순위 정하는 class를 따로 만들어서 sort를 위해 compareTo()함수를 오버라이딩했다. 사실 이 문제 처음 풀 때는 그냥 하나 하나 비교해야 겠다고 생각했는데 스터디하면서 이런 방법이 있다는 것을 알게 됐다.

static class Ranking implements Comparable<Ranking> {
        int score;
        int cnt;
        int time;
        int id;

        Ranking(int score, int cnt, int time, int id) {
            this.score = score;
            this.cnt = cnt;
            this.time = time;
            this.id = id;
        }

        @Override
        public int compareTo(Ranking s){
            if(this.score < s.score) return 1;
            else if(this.score == s.score){
                if(this.cnt > s.cnt) return 1;
                else if(this.cnt == s.cnt){
                    if(this.time > s.time) return 1;
                    else return -1;
                }
                else return -1;
            }
            else return -1;
        }
    }

요롷게 Ranking 클래스에서 compareTo()를 만들어 놓으면 Ranking 배열에 대해 Arrays.sort(랭킹타입배열)이 내림차순으로 정렬된다!

너무 신기한 알고리즘의 세계..!

전체 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        String input = br.readLine();
        int t = Integer.parseInt(input);

        while(t --> 0) {
            input = br.readLine();
            int n, k, id, m;
            StringTokenizer st = new StringTokenizer(input);
            n = Integer.parseInt(st.nextToken());   // 팀 개수
            k = Integer.parseInt(st.nextToken());   // 문제 개수
            id = Integer.parseInt(st.nextToken());  // 나의 팀 아이디
            m = Integer.parseInt(st.nextToken());   // 로그 개수

            int score[][] = new int[n+1][k+1];  // 팀별 문제별 점수
            int cnt[] = new int[n+1];           // 팀별 제출 횟수
            int time[] = new int[n+1];          // 팀별 마지막 제출 시간

            // m개의 로그 읽어서 저장
            int index = 0;
            while(m --> 0) {
                input = br.readLine();
                st = new StringTokenizer(input);
                int a, b, c;
                a = Integer.parseInt(st.nextToken());   // 팀 id
                b = Integer.parseInt(st.nextToken());   // 문제번호
                c = Integer.parseInt(st.nextToken());   // 획득점수

                score[a][b] = Math.max(score[a][b], c);
                cnt[a]++;
                time[a] = index;
                index++;
            }

            Ranking res[] = new Ranking[n];
            for(int i = 1; i<=n; i++){
                int sum = 0;
                for(int j = 1; j<=k; j++){
                    sum += score[i][j];
                }
                res[i-1] = new Ranking(sum, cnt[i], time[i], i);
            }
            Arrays.sort(res);
            for(int i = 0; i<n; i++){
                if(res[i].id == id){
                    bw.write(Integer.toString(i+1)+'\n');
                }
            }
        }
        bw.flush();
        bw.close();
        br.close();
    }
    static class Ranking implements Comparable<Ranking> {
        int score;
        int cnt;
        int time;
        int id;

        Ranking(int score, int cnt, int time, int id) {
            this.score = score;
            this.cnt = cnt;
            this.time = time;
            this.id = id;
        }

        @Override
        public int compareTo(Ranking s){
            if(this.score < s.score) return 1;
            else if(this.score == s.score){
                if(this.cnt > s.cnt) return 1;
                else if(this.cnt == s.cnt){
                    if(this.time > s.time) return 1;
                    else return -1;
                }
                else return -1;
            }
            else return -1;
        }
    }
}