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

- 문제 : https://www.acmicpc.net/problem/9017

 

문제 이해 

- 생각보다 조건이 까다로워서 시간이 좀 걸렸던 문제다. 이해한 문제 조건으로는 다음과 같다. 

- 달리는 사람들은 모두 팀에 속해있고, 팀의 총 인원이 6명 미만인 팀은 점수 계산에서 제외된다. 

- 팀의 점수를 산출하는 방식은 상위 4명의 점수를 합하는 것이다. 

- 살아남은 각 팀의 팀원들 중 상위 4명의 점수를 합산해서 가장 적은 점수를 얻은 팀이 우승하게 된다. 

 

-> 위 조건을 보면 알겠지만, 일단 팀 별로 조건에 맞는 팀원의 수를 구해야 하고, 그 중 팀 수가 6명 미만인 팀은 제외해야 한다. 

-> 이제 각 남은 팀 중에서 상위 4명의 점수를 구한 뒤 정렬해서 우승한 팀을 출력해야 하는 문제다. 

-> 만약 4등까지의 점수 합이 같은 두 팀이 있을 때는 5등의 점수도 비교해야 한다. 

-> 자격을 갖춘 팀을 먼저 구해야하는 것을 간과해 헤맸던 문제다. 

 

풀이 로직

- 각 입력값을 n과 scores에 입력 받은 뒤, 각 팀의 자격 여부를 확인하기 위해 팀의 인원수를 구해야한다. 

- 각 팀의 인원수는 Counter 라이브러리를 이용해 {팀 번호 : 사람 수 }의 certified 딕셔너리를 만든다 

- 만약 자격이 안되는 팀이라면 {팀 번호 : -1} 처리를 해준다. (딕셔너리에서 빼면 나중에 에러가 발생한다)

- 살아남은 팀들의 점수를 result 딕셔너리({팀 번호 : [점수 배열]})에 저장하는데, 자격이 있는 팀들(딕셔너리 값이 -1이 아닌)의 점수를 배열에 추가한다. scores의 순서대로 점수를 부여하므로 score 변수를 이용하고, 반복문을 하나씩 돌 때마다 + 1해준다. 

- 각 팀에서 4명까지의 점수를 합해서 우승 팀을 가려야 하는데, 여기에서 또 어려운 점이 있다. 

    - 만약 4등까지의 점수 합이 동일한 경우 5등의 점수를 비교해서 더 낮은 팀이 우승 후보가 된다. 

    - 그래서 먼저 4등까지의 점수 합(num_sum)을 구한 뒤 추가로 fifth 변수에 5등의 점수도 추가한다. 

    - 그래서 만약 num_sum과 4등까지의 합이 같은 팀이 있는 경우에는 5등의 점수를 비교하면 된다. 

 

 

정답 풀이 

from collections import Counter
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    scores = list(map(int, input().split()))

    certified = Counter(scores)
    for x in certified.keys():
        if certified[x] < 6 : 
            certified[x] = -1
             
    result = {}   # {팀 번호 : [점수 배열]}
    score = 1
    for i in range(len(scores)):
        temp = scores[i]
        if certified[temp] != -1:
            if temp in result:
                result[temp].append(score)
            else:
                result[temp] = [score]
            score += 1

    answer = -1
    fifth = 0
    num_sum = 1e9
    for team, num_arr in result.items():
        if num_sum > sum(num_arr[:4]):
            answer = team
            fifth = num_arr[4]
            num_sum = sum(num_arr[:4])
        elif num_sum == sum(num_arr[:4]):
            if num_arr[4] < fifth:
                answer = team
                fifth = num_arr[4]
                num_sum = sum(num_arr[:4])
    print(answer)