[백준/JAVA] 9017번: 크로스 컨트리

📖 문제

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

 

 

 

💡  풀이 방식

• 구현

필요 자료구조
- 등수 저장용 int형 배열 (ranks)
- 각 팀별 인원 수 저장용 Map (cntMap)
- 가장 큰 숫자의 팀 번호 저장용 int형 변수
- 해당 팀의 5번째 선수 저장용 배열 (fifth)
-  팀 별 최종 점수 저장용 Map (scoreMap)
-  6명 이상인 팀 별로 몇 명 있는지 저장용 Map (tmpMap)
- 가장 낮은 점수 저장용 int형 변수 (result)
- 5번째 점수 저장용 int형 변수 (fifthScore)

 

. N개의 등수를 입력받는다.

    - ranks 배열에 저장한다.

    - 각 팀 별 팀원 수를 cntMap에 저장한다.

    - 가장 큰 번호의 팀 teamNum을 현재 등수를 비교해 더 큰 값으로 갱신한다.

 

 

. 입력받은 등수들(ranks 배열)을 순회하며 팀 별로 점수를 계산한다.

    - 팀원이 6명인 경우에만 아래 과정을 진행한다. (cntMap.get(r) == 6)

      ㄴ 현재 팀 r의 명수를 +1해 갱신한다.

      ㄴ 현재 팀 r의 상위 4명의 주자 범위 안에 들어와 있다면, 점수를 누적해 저장한다. (scoreMap.put(r, scoreMap.getOrDefault(r, 0) + score)

      ㄴ 현재 팀 r의 5번째 선수라면, 현재 점수를 팀 별 5번째 선수의 점수를 저장하는 배열에 기록한다. (fifth[r] = score)

 

 

. scoreMap을 순회하며 가장 낮은 점수를 가진 팀을 구한다. 점수가 동점일 경우, 5번째 선수의 점수가 가장 낮은 팀을 우승팀으로 출력한다.

    - 현재 팀의 점수(scoreMap.get(key))가 가장 낮은 점수 result보다 작다면, 가장 낮은 점수를 더 작은 값으로 갱신한다. 그리고 가장 작은 5번째 점수를 현재 팀의 5번째 주자의 값으로 변경한다.

    - 현재 팀의 점수(scoreMap.get(key))가 가장 낮은 점수 result와 동점이라면,  현재 팀의 5번째 선수의 점수가 전역 변수 fifthScore보다 작은 경우에만 우승팀으로 인정한다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
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());
        int[] answer = new int[T];
        
        for(int i = 0 ; i < T ; i++) {
            int N = Integer.parseInt(br.readLine());
            
            int[] ranks = new int[N];   // Ｎ등까지 존재
            Map<Integer, Integer> cntMap = new HashMap<>(); // 각 팀별 인원수 세기
            int teamNum = Integer.MIN_VALUE;    // 가장 큰 번호의 팀 （팀 수 구하기용）
            
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 0 ; j < N ; j++) {
                int x = Integer.parseInt(st.nextToken());
                
                cntMap.put(x, cntMap.getOrDefault(x, 0) + 1);
                ranks[j] = x;
                teamNum = Math.max(teamNum, x);
            }
            
            int[] fifth = new int[teamNum + 1]; // 해당 팀의 ５번째 선수 저장용 배열
            Map<Integer, Integer> scoreMap = new HashMap<>();
            Map<Integer, Integer> tmpMap = new HashMap<>(); // 팀 별로 누적해 점수 계산용 Map
            int score = 1;
            
            for(int r : ranks) {
                if(cntMap.get(r) == 6) {   // 팀원이 ６명인 경우에만
                    tmpMap.put(r, tmpMap.getOrDefault(r, 0) + 1);
                    
                    if(tmpMap.get(r) <= 4)  // 해당 팀의 ４등까지만 점수 기록
                        scoreMap.put(r, scoreMap.getOrDefault(r, 0) + score);
                   
                    if(tmpMap.get(r) == 5)  // 해당 팀의 ５번째 선수의 점수
                        fifth[r] = score;
                        
                    score++;
                }
            }
            
            int result = Integer.MAX_VALUE;     // 가장 낮은 점수
            int fifthScore = Integer.MAX_VALUE; // 5번째 점수
            
            for(Integer key : scoreMap.keySet()) {
                int tmp = scoreMap.get(key);
                
                if(tmp < result) {  // 점수가 가장 낮은 팀이 우승
                    result = tmp;
                    fifthScore = fifth[key];
                    answer[i] = key;
                }
                else if(tmp == result) {    // 점수가 동점일 경우, 5번째 선수의 점수가 낮을 때 우승
                    if(fifthScore > fifth[key])
                        answer[i] = key;
                }
            }
        }
        
        // 출력하기
        for(int i : answer) {
            System.out.println(i);
        }
    }
}

 

 

 

➕ 다른 풀이 방식

- 점수 구할 때 람다식 사용하심

[백준][BOJ 9017] - 크로스 컨트리

 

- 점수 구할 때 우선순위 큐 &람다식 사용하심

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

 

---

💦 어려웠던 점

- Map을 이리 여러 번 사용할 줄 몰랐다,,,,

- 자료구조를 먼저 생각하는 것이 가장 중요한 듯,,

 

 

🧐 새로 알게 된 내용

X

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

백준 9017번: 크로스 컨트리[JAVA]