[Baekjoon] 9017 크로스 컨트리 (Java)

문제 링크

백준- 9017: 크로스 컨트리

문제

총 N명의 선수의 점수가 주어진다.
완주한 순서대로 주어지므로 주어지는 순서가 해당 선수의 등수이다.
해당 선수의 팀이 입력값으로 주어진다.

3
1 2 1

위와 같은 경우
1등 : 1번팀
2등 : 2번팀
3등 : 3번팀
을 의미한다.

조건은 다음과 같다.
1. 팀원의 수가 6명 이하인 경우 등수에서 제외한다.
2. 각 팀에서 점수가 높은(더 빨리 완주한) 선수 4명의 점수만 합산한다.
3. 합산 점수가 같은 경우 5번째 선수의 등수에 따라 결과를 낸다.

풀이

구현을 하다보니 뭔가 조건이 복잡하게 느껴졌다. 조금 깔끔하게 코드를 짜보려고 욕심을 냈었는데, 쉽지 않았던 것 같다.

입력 크기가 작은 것을 보면 그냥 정직하게 구현하면 될 것이라는 걸 알 수 있었다. 이런 구현문제는 애매하게 효율적으로 풀기보단 정직하게 변수명을 잘 설정해가며 풀어야할 것 같다. 보통 코딩테스트는 가독성이 필요없지만 구현 분류의 문제에서는 어느정도 신경을 써야한다.

다음의 순서로 문제를 해결했다.

1. 입력값을 arr배열에 저장한다. 저장함과 동시에 해당 팀의 참가인원을 countParticipants배열에 업데이트 하며 저장하고 5번째 선수인 경우 fifth배열에 등수를 저장한다.

2. 점수를 계산한다. 팀원이 6명보다 작은 팀을 제외하는 작업을 tmp변수를 이용해 계산했다. tmp값이 의미하는 바는 i번째 선수보다 먼저 들어온 선수들 중 팀이 참가조건(6명)을 충족하지 못 한 선수의 수이다. 즉 참가조건을 만족한 팀의 점수를 score배열에 업데이트 하는 과정에서 tmp값을 추가로 고려해 계산한다.

countCheck를 통해 현재 확인한 선수의 수를 팀별로 기록한다. 만약 4명을 모두 확인했다면 이후의 선수를 팀의 점수에 포함하지 않는다.
countCheck[i] == 5인 경우는 i번째 팀의 5번째 선수임을 의미한다. 따라서 해당 선수의 점수를 fifth배열에 저장한다.

3. 가장 점수가 낮은 팀을 찾는다. 점수가 같을 경우 fifth값을 비교해 우승팀을 선정한다.

코드

import java.io.*;
import java.util.*;

public class Main{

    private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));

    //1. 6명 이상
    //2. 점수가 같으면 5번째 선수 비교
    //3. 6명 이하인 팀은 제외
    private static void solve() throws IOException {
        int N = Integer.parseInt(br.readLine());
        int teamCount= 0;
        int[] arr = new int[N+1];
        int[] countParticipants = new int[202];
        int[] countCheck = new int[202];
        int[] score = new int[202];
        int[] fifth = new int[202];

		//1
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            countParticipants[arr[i]]++;
            teamCount = Math.max(teamCount, arr[i]);
        }
        
		//2
        int tmp = 0;
        for(int i=1; i<=N; i++){
            if(countParticipants[arr[i]] < 6) {
                tmp++; score[arr[i]] = Integer.MAX_VALUE; fifth[arr[i]] = Integer.MAX_VALUE;
            }
            else if(countCheck[arr[i]] < 4) {
                score[arr[i]] += i-tmp;
                countCheck[arr[i]]++;
            }
            else if(countCheck[arr[i]] == 4) {
                fifth[arr[i]] = i - tmp;
                countCheck[arr[i]]++;
            }
        }

		//3
        int bestTeam = 0, bestScore = Integer.MAX_VALUE;
        fifth[0] = Integer.MAX_VALUE;

        for(int i=1; i<=teamCount; i++){
            if(score[i] < bestScore){
                bestScore = score[i];
                bestTeam = i;
            }
            else if(score[i] == bestScore && fifth[i] < fifth[bestTeam]){
                bestTeam = i;
            }
        }
        System.out.println(bestTeam);
    }

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int T = Integer.parseInt(st.nextToken());
        while(T-->0){
            solve();
        }
    }
}

구현은 측정 난이도에 비해 더 어렵게 느껴진다. 많이 풀어봐야겠다.