[Java] 백준 9017 크로스 컨트리

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

난이도

실버3

문제

크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다.

한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.

예를 들어, 다음의 표를 살펴보자.

등수 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
팀 A B C C A C B D A A C A C C A
점수 1 n/a 2 3 4 5 n/a n/a 6 7 8 9 10 11 12
팀 B 와 D 는 선수의 수가 여섯이 아니므로, 점수를 받을 수 없다. 팀 A 의 점수는 18 (1+4+6+7)이고, 팀 C 의 점수는 18 (2+3+5+8)이다. 이 경우 두 팀의 점수가 같으므로 다섯 번째로 결승점을 통과한 선수를 고려한다, A 팀의 다섯 번째 선수의 점수가 C 팀의 다섯 번째 선수의 점수보다 적으므로 A 팀이 우승팀이 된다.

모든 선수들의 등수가 주어질 때, 우승팀을 구하는 프로그램을 작성하라. 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 여섯 명 보다 많은 선수가 참가하는 팀은 없고, 적어도 한 팀은 참가 선수가 여섯이며, 모든 선수는 끝까지 완주를 한다고 가정한다.

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (6 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 팀 번호를 나타내는 N 개의 정수 t1, t2, …, tN 이 공백을 사이에 두고 주어진다. 각 팀은 1 과 M(1 ≤ M ≤ 200)사이의 정수로 표현된다.

출력

출력은 표준출력을 사용한다. 하나의 테스트 케이스에 대한 우승팀의 번호를 한 줄에 출력한다.

내 코드

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

class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int tc = 0; tc < T; tc++) {
			int N = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine());
		
			int[] team = new int[N];
			HashMap<Integer, Integer> count = new HashMap<>();
			for(int i = 0; i < N; i++) {
				int tmp = Integer.parseInt(st.nextToken());
				team[i] = tmp;
				if(count.containsKey(tmp)) {
					count.replace(tmp, count.get(tmp) + 1);
				}else {
					count.put(tmp, 1);
				}
			}
			
			HashSet<Integer> under = new HashSet<>();
			for(Integer key: count.keySet()) {
				if(count.get(key) < 6) {
					under.add(key);
				}
			}
			
			int personalScore = 1;
			HashMap<Integer, int[]> score = new HashMap<>(); 
            // 4등까지 점수, 5등 점수, 현재 더한 사람의 수
			for(int i = 0; i < N; i++) {
				if(!under.contains(team[i])) {
					if(score.containsKey(team[i])) {
						int[] tmp = score.get(team[i]);
						if(tmp[2] < 4) {
							tmp[0] += personalScore++;
						}else if(tmp[2] == 4) {
							tmp[1] = personalScore++;
						}else {
							personalScore++;
						}
						tmp[2]++;
						score.replace(team[i], tmp);
					}else {
						score.put(team[i], new int[]{personalScore++, 0, 1});
					}
				}
			}
			
			int winner = -1, totalScore = 10000, five = 10000;
			for(Integer key : score.keySet()) {
				int[] now = score.get(key);
				if(totalScore>now[0] || (totalScore == now[0] && five > now[1])) {
					winner = key;
					totalScore = now[0];
					five = now[1];
				}
			}
			System.out.println(winner);
		}
	}
}

일단 순서대로 입력을 저장할 team 리스트를 선언하고,
HashMap을 통해서 각 팀별로 몇명인지를 카운트 하였다.

그 후, 6명 미만이라면 조건에 성립하지 않아 따로 관리할 필요가 있는 팀은
under이라는 HashSet을 선언하여 저장하였다.

그 후 team 리스트에서 6명 미만인 사람의 점수는 제외하면서 점수를 확인해야하기 때문에
personalScore라는 변수를 선언하여 각각의 점수를 더해줄 예정이다.

그리고 우승팀을 판별하기 위해서,
팀의 번호를 Key로 하고
4등까지의 점수 합, 5등의 점수, 그리고 카운팅 된 사람의 수를 저장할 int[]를 Value로 하는
또 다른 HashMap인 score를 선언하였다.

for 문을 통해
1. under에 속하지 않는 team만 확인한다.
2. score 안에 이미 선언 되어있는가를 확인한다.
3. int[] 안에 4명까지는 0번 인덱스의 개별 점수를 추가하고, 5번째 사람은 1번 인덱스에 개별 점수 저장, 몇번째까지 확인했는지 사람의 수를 카운팅하는건 2번 인덱스에서 관리했다.

우선순위큐를 통해 우승팀을 구해도 될 것 같긴 하지만 난 반복문으로 전체 팀을 확인했다.
점수 더 작은지 비교하기 위한 totalScore,
다섯번째 사람의 점수를 비교하기 위한 five를 선언하여 우승팀을 판별하였다.