백준 9017 크로스 컨트리 자바(java)

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

9017번: 크로스 컨트리

 

풀이 방법

점수를 매길 때 팀의 주자가 여섯 주자가 되지 않으면 제외시켜야 한다.

따라서, 먼저 팀 번호를 인덱스로 하는 1차원 배열 cnt를 만들고 입력 받은 팀 번호 t 에 따라 cnt[t] 의 값을 1씩 증가시키면서 팀별 주자들을 카운트한다.

그 다음, 다시 입력 받은 팀 번호를 순서대로 순회하면서 점수 1부터 증가시키면서 점수를 매기는데 이때 cnt 배열을 이용하여 cnt[t] 가 6인 경우에만 점수를 매기고 저장한다. 점수 저장은 HashMap 에 key 를 팀 번호, value 를 주자들의 점수 리스트로 하여 저장할 수 있도록 하였다. 점수를 다 매기고 저장한 후 HashMap 의 key, 즉 팀 번호를 순회하면서 각 팀의 상위 네명의 합을 구하고 더 작은 합일 때 우승, 같다면 다섯 번째 주자의 점수가 더 작은 경우에 우승하도록 한다.

 

코드

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));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            int n = Integer.parseInt(br.readLine());
            String[] line = br.readLine().split(" ");

            int[] cnt = new int[n+1]; // 주자 카운트 배열
            HashMap<Integer, List<Integer>> map = new HashMap<>(); // 각 팀별 점수 기록
            // 각 팀의 주자 카운트
            for(int j=0; j<n; j++) {
                cnt[Integer.parseInt(line[j])] += 1;
            }

            int rank = 1; // 점수
            for(int j=0; j<n; j++) {
                int teamNum = Integer.parseInt(line[j]);
                if(cnt[teamNum] == 6) { // 여섯 주자 이상 참가한 팀만 점수 매김
                    if(!map.containsKey(teamNum)) {
                        map.put(teamNum, new ArrayList<>());
                    }
                    if(map.get(teamNum).size() < 5) {
                        map.get(teamNum).add(rank);
                    }
                    rank++;
                }
            }

            int winner = 0;
            int minSum = Integer.MAX_VALUE;
            int fifthRank = Integer.MAX_VALUE;
            for(Integer team : map.keySet()) {
                List<Integer> rankList = map.get(team);
                // 상위 네명의 주자 점수 합 구하기
                int sum = 0;
                for(int j=0; j<4; j++) {
                    sum += rankList.get(j);
                }
                // 점수 합이 작은 것이 우승
                if(minSum > sum) {
                    minSum = sum;
                    winner = team;
                    fifthRank = rankList.get(4);
                    // 같은 경우 다섯번쨰 주자의 등수 비교
                } else if(minSum == sum) {
                    if(fifthRank > rankList.get(4)) {
                        fifthRank = rankList.get(4);
                        winner = team;
                    }
                }
            }
            System.out.println(winner);
        }
    }
}