https://www.acmicpc.net/problem/9017
9017번: 크로스 컨트리
입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의
www.acmicpc.net
풀이 방법
점수를 매길 때 팀의 주자가 여섯 주자가 되지 않으면 제외시켜야 한다.
따라서, 먼저 팀 번호를 인덱스로 하는 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);
}
}
}'알고리즘 > baekjoon' 카테고리의 다른 글
| 백준 2644 촌수계산 자바(java) (0) | 2024.01.14 |
|---|---|
| 백준 9081 단어 맞추기 자바(java) (1) | 2023.12.21 |
| 백준 14501 퇴사 자바(java) (1) | 2023.12.21 |
| 백준 19236 청소년 상어 자바(java) (1) | 2023.12.20 |
| 백준 14889 스타트와 링크 자바(java) (1) | 2023.12.19 |