서론
구현 문제입니다.
이것저것 생각하다 defaultdict를 여러개 사용하여 해결했습니다.
난이도
실버 3
문제
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 128 MB |
크로스 컨트리 달리기는 주자들이 자연적인 야외의 지형에 만들어진 코스를 달리는 운동 경기이다. 경주 코스는 일반적으로 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 팀이 우승팀이 된다.
모든 선수들의 등수가 주어질 때, 우승팀을 구하는 프로그램을 작성하라. 각 팀의 참가 선수가 여섯보다 작으면 그 팀은 점수 계산에서 제외됨을 주의하라. 여섯 명 보다 많은 선수가 참가하는 팀은 없고, 적어도 한 팀은 참가 선수가 여섯이며, 모든 선수는 끝까지 완주를 한다고 가정한다.
입력
입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 케이스로 주어진다. 입력 파일의 첫 번째 줄에 테스트 케이스의 수를 나타내는 정수 T 가 주어진다. 두 번째 줄부터는 두 줄에 하나의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 하나의 정수 N (6 ≤ N ≤ 1,000)이 주어진다. 두 번째 줄에는 팀 번호를 나타내는 N 개의 정수 t1, t2, …, tN 이 공백을 사이에 두고 주어진다. 각 팀은 1 과 M(1 ≤ M ≤ 200)사이의 정수로 표현된다.
출력
출력은 표준출력을 사용한다. 하나의 테스트 케이스에 대한 우승팀의 번호를 한 줄에 출력한다.
예시
예제 입력 1
2
15
1 2 3 3 1 3 2 4 1 1 3 1 3 3 1
18
1 2 3 1 2 3 1 2 3 3 3 3 2 2 2 1 1 1예제 출력 1
1
3풀이
간편한 저장을 위해 Counter와 defaultdict를 사용하였습니다.
배열(rank)을 입력받으면 cnt에는 팀 별 선수의 수가 저장됩니다.
그 후, rank를 순서대로 탐색하며 현재 팀의 선수가 6명인 경우에만 팀 별 선수에 점수를 추가합니다.
len(team[i]) < 5의 조건이 두 번이나 나온 이유는 5번째 선수 까지의 점수와 4번째 선수까지의 통합점수가 필요하기 때문입니다.
탐색 도중 5번째 선수에 도달하면, team[i].append(score)를 통해 team에 저장됩니다.
append를 통해 team[i]에는 5명이 되었기 때문에, total[i] += score 코드는 실행되지 않습니다.
탐색이 끝나면, 선수가 6명인 팀만 선별되어
team에는 5번째 선수까지의 점수,
total에는 4번째 선수까지의 점수 합산
이 저장되게 됩니다.
가장 낮은 통합 점수를 가진 팀들을 선별하여 ans에 해당 팀의 번호를 key로, 5번째 선수의 점수를 value로 저장해줍니다.
그 후, ans를 5번째 선수 기준으로 오름차순 정렬을 해준 후 가장 앞 팀의 번호를 출력해줍니다.
코드
import sys
from collections import Counter, defaultdict
input = sys.stdin.readline
for _ in range(int(input())):
n = int(input())
rank = list(map(int, input().split()))
cnt = Counter(rank) # 참가 인원의 수를 세기 위한 Counter
team = defaultdict(list) # 각 팀 별 점수 저장을 위한 dictionary
total, ans = defaultdict(int), defaultdict(int) # 각 팀 별 총 점수와 정답을 찾기 위한 dictionary
score = 1 # 들어온 순서대로의 점수
for i in rank:
if cnt[i] > 5: # 현재 팀의 참가 인원이 6명인 경우
if len(team[i]) < 5: # 5등까지의 점수만 필요하기 때문에 범위 설정
team[i].append(score) # 팀 별 점수 저장
if len(team[i]) < 5: # 4등까지의 통합 점수 비교를 위한 범위 설정
total[i] += score
score += 1 # 점수 증가
min_score = min(total.values()) # 총 점수 중 가장 낮은 점수
for k, v in total.items():
if v == min_score:
ans[k] = team[k][-1] # 가장 낮은 점수인 경우에 해당 팀의 5번째 선수를 ans에 추가
# ans에서 5번째 선수를 기준으로 정렬 후 가장 점수가 낮은 팀 출력
print(sorted(ans.items(), key=lambda x: x[1])[0][0])실행 결과
