[Java] 백준 3758 KCPC

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

난이도

실버2

문제

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다.

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다.

최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다.
최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.
동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라.

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다.

출력

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

class Main {

	static class Team {
		int idx, tryCnt, lastSubmit;
		HashMap<Integer, Integer> hm;

		public Team(int idx, int tryCnt, int lastSubmit, HashMap<Integer, Integer> hm) {
			this.idx = idx;
			this.tryCnt = tryCnt;
			this.lastSubmit = lastSubmit;
			this.hm = hm;
		}
	}

	public static void main(String[] args) throws IOException {
		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 P = Integer.parseInt(st.nextToken()); // 문제의 수
			int M = Integer.parseInt(st.nextToken()); // 나의 팀 id
			int L = Integer.parseInt(st.nextToken()); // 로그의 수
			Team[] team = new Team[N + 1];

			for (int i = 1; i <= N; i++) {
				team[i] = new Team(i, 0, 0, new HashMap<>());
			}

			for (int i = 0; i < L; i++) {
				st = new StringTokenizer(br.readLine());
				int idx = Integer.parseInt(st.nextToken());
				int pIdx = Integer.parseInt(st.nextToken());
				int score = Integer.parseInt(st.nextToken());

				team[idx].lastSubmit = i;
				team[idx].tryCnt++;
				int tmpScore = team[idx].hm.getOrDefault(pIdx, 0);
				team[idx].hm.put(pIdx, Math.max(tmpScore, score));
			}

			int before = 0;
			int myScore = getScore(team[M].hm);
			int myLastSubmit = team[M].lastSubmit;
			int myTryCnt = team[M].tryCnt;

			for (Team t : team) {
				if (t == null || t.idx == M)
					continue;

				int nowScore = getScore(t.hm);
				if (nowScore > myScore) {
					before++;
					continue;
				}
				if (nowScore == myScore && t.tryCnt < myTryCnt) {
					before++;
					continue;
				}
				if (nowScore == myScore && t.tryCnt == myTryCnt && t.lastSubmit < myLastSubmit) {
					before++;
					continue;
				}
			}
			sb.append(before + 1).append("\n");
		}
		System.out.println(sb);
	}

	public static int getScore(HashMap<Integer, Integer> hm) {
		int ret = 0;
		for (Integer k : hm.keySet()) {
			ret += hm.get(k);
		}
		return ret;
	};
}

팀에 저장이 되어야 하는 정보를 class로 저장하였다.
팀의 idx, tryCnt, lastSubmit, HashMap을 저장했는데,
앞에 세 개는 예측 가능한 그대로이고 HashMap은 각 문제별 최고 점수를 저장하기 위해서이다.

로그를 하나 볼 때마다 마지막 제출을 업데이트하고, 시도 횟수를 +1 하고,
getOrDefault를 통해 이미 있다면 저장된 정보, 없다면 0을 반환하여
최고 점수를 비교하여 다시 저장한다.

PriorityQueue 혹은 정렬을 통해서 찾을 수 있을 것 같지만 나는 그냥
내가 궁금한 팀의 정보를 저장해두고, 반복문으로 전체를 한번씩만 확인하면서 등수를 찾았다.