[백준 9017번] 크로스 컨트리 - 파이썬

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

9017번: 크로스 컨트리

 

💡문제 분석 요약

크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 4에서 12 킬로미터이며, 숲이나 넓은 땅을 통과하는 풀과 흙으로 된 지면과 언덕과 평평한 지형을 포함한다. 이 경기는 주자들의 개인성적을 매기고, 이를 가지고 팀의 점수를 계산한다. 

한 팀은 여섯 명의 선수로 구성되며, 팀 점수는 상위 네 명의 주자의 점수를 합하여 계산한다. 점수는 자격을 갖춘 팀의 주자들에게만 주어지며, 결승점을 통과한 순서대로 점수를 받는다. 이 점수를 더하여 가장 낮은 점수를 얻는 팀이 우승을 하게 된다. 여섯 명의 주자가 참가하지 못한 팀은 점수 계산에서 제외된다. 동점의 경우에는 다섯 번째 주자가 가장 빨리 들어온 팀이 우승하게 된다.

예를 들어, 다음의 표를 살펴보자.

 

등수	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
팀	A	B	C	C	A	C	B	D	A	A	C	A	C	C	A
점수	1	n/a	2	3	4	5	n/a	n/a	6	7	8	9	10	11	12

팀 B 와 D 는 선수의 수가 여섯이 아니므로, 점수를 받을 수 없다. 팀 A 의 점수는 18 (1+4+6+7)이고, 팀 C 의 점수는 18 (2+3+5+8)이다. 이 경우 두 팀의 점수가 같으므로 다섯 번째로 결승점을 통과한 선수를 고려한다, A 팀의 다섯 번째 선수의 점수가 C 팀의 다섯 번째 선수의 점수보다 적으므로 A 팀이 우승팀이 된다.

모든 선수들의 등수가 주어질 때, 우승팀을 구하는 프로그램을 작성하라. 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 여섯 명 보다 많은 선수가 참가하는 팀은 없고, 적어도 한 팀은 참가 선수가 여섯이며, 모든 선수는 끝까지 완주를 한다고 가정한다.

💡알고리즘 설계

count 해시에 각 팀의 팀원 수를 저장한다.

point 해시에 각 팀의 선수가 얻은 점수를 배열으로 저장한다.

 

1. 해시를 이용해 팀원의 수를 저장한다.

2. for문을 이용해 팀을 하나씩 입력받고, 팀원이 6명인 팀이면 현재 점수를 1 더한 후, 해당 팀의 해시에 저장된 배열에 현재 점수를 추가한다.

(선수가 6명이 아닌 팀이 있으면 그 선수는 없는 것으로 처리한 후 등수가 점수가 된다. 따라서 팀의 선수가 6명일 때 만 점수에 1을 더한 후 각 팀의 점수 저장 배열에 추가한다.)

3. 람다를 이용해 각 팀의 배열에서 1,2,3,4등의 합과, 4번째 등수의 점수가 낮은 순으로 정렬한다.

4. 가장 앞에 있는 팀을 출력한다.

 

💡코드

import sys
input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N=int(input())
    count={}
    point={}
    team=list(map(int, input().split()))
    
    # 팀원 수 세기
    for i in range(N):
        if team[i] in count:
            count[team[i]]+=1
        else:
            count[team[i]]=1

    # 점수 더하기
    pt=0
    for i in range(N):
        if count[team[i]]==6:
            pt+=1
            if team[i] in point:
                point[team[i]].append(pt)
            else:
                point[team[i]]=[pt]

    sorted_team=sorted(point, key=lambda x:(sum(point[x][0:4]), point[x][4]))
    print(sorted_team[0])

 

💡 느낀점 or 기억할 정보

문제를 똑바로 안읽어서 굉장히 헷갈렸다...

처음엔 point배열에 점수를 따로 입력받아 배열의 형태로 저장하지 않고, 아예 총합 점수만을 계산했는데 그러니 4번째 선수의 점수를 기록하기 힘들어서 각 팀별로 점수 배열을 입력받았다.

점수 배열을 저장할 때 해시 말고 list를 써도 될 것 같은데 해시가 쓰기 편할 것 같아 해시를 이용했다.