첫 시도
- 2차원 배열을 만든다. 행은 팀을, 열은 문제를 뜻한다.
- 2차원 배열에 점수를 저장한다 -> 이때 저장되어있는 값과 새로 문제를 풀어 얻게 된 값중 큰 값을 저장한다.
- 모든 로그를 확인한 후 각 문제의 최대 점수를 더해 팀별로 저장한다.
- Team 클래스 생성 -> id, 점수 총합, 푼 횟수, 마지막으로 풀은 순서를 Team에 담아 배열로 만든다 -> Team 배열 정렬(Team 클래스에 impleaments 한 Comparable 조건에 따라 정렬된다)
- 시간 복잡도는 O(MK+N^2)이다.
해결
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int t = Integer.parseInt(br.readLine());
for(int i = 0; i<t; i++) {
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[][] input = new int[N+1][K+1];
int[] sum = new int[N+1];
int[] last = new int[N+1];
int lastTime = 0;
for(int j = 0; j<M; j++) {
st = new StringTokenizer(br.readLine());
int id = Integer.parseInt(st.nextToken());
int pNum = Integer.parseInt(st.nextToken());
int score = Integer.parseInt(st.nextToken());
input[id][pNum] = Math.max(input[id][pNum], score);
input[id][0]++;
last[id] = lastTime++;
}
Team team[] = new Team[N];
for(int j = 1; j<N+1; j++){
int temp = 0;
for(int k = 1; k<K+1; k++){
temp += input[j][k];
}
team[j-1] = new Team(j,temp,input[j][0],last[j]);
}
Arrays.sort(team);
int rank = 1;
for(Team a : team){
if(T == a.id) System.out.println(rank);
else rank++;
}
}
}
}
class Team implements Comparable<Team>{
int id;
int score;
int count;
int time;
public Team(int id, int score, int count, int time) {
this.id = id;
this.score = score;
this.count = count;
this.time = time;
}
@Override
public int compareTo(Team o) {
if(this.score < o.score){
return 1;
}
else if(this.score == o.score){
if(this.count > o.count){
return 1;
}
else if(this.count == o.count){
if(this.time > o.time){
return 1;
}
return -1;
}
return -1;
}
return -1;
}
}