문제
프로그래밍 대회에서 팀별로 문제당 최고 점수의 합으로 순위를 매긴다. 동점이면 제출 횟수가 적은 팀, 그래도 같으면 마지막 제출이 빠른 팀이 앞선다.
입력
테스트 케이스 수, 각 케이스에 팀 수 N, 문제 수 K, 내 팀 번호 T, 제출 수 L과 각 제출 정보가 주어진다.
출력
각 테스트 케이스마다 내 팀의 순위를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3 4 2 8 1 1 30 2 3 30 1 2 40 2 1 20 3 1 30 1 1 20 2 3 10 3 4 20 | 1 |
풀이
각 팀의 문제별 최고 점수, 제출 횟수, 마지막 제출 시간을 추적하여 정렬한다.
- 각 제출에 대해 해당 팀의 문제별 최고 점수를 갱신한다
- 제출 횟수와 마지막 제출 시간을 기록한다
- 총점 내림차순, 제출 횟수 오름차순, 마지막 제출 시간 오름차순으로 정렬한다
- 내 팀의 순위를 찾아 출력한다
핵심 아이디어: 문제당 최고 점수만 반영하므로, 2차원 배열로 팀별 문제별 최고 점수를 관리하면 된다.
코드
import sys
case = int(sys.stdin.readline().rstrip())
for i in range(case):
n, k, t, l = map(int, sys.stdin.readline().split(" "))
score = [[0 for _ in range(k)] for _ in range(n)]
submit = [0 for _ in range(n)]
time = [0 for _ in range(n)]
for j in range(l):
ex = list(map(int, sys.stdin.readline().split(" ")))
score[ex[0] - 1][ex[1] - 1] = max(score[ex[0] - 1][ex[1] - 1], ex[2])
submit[ex[0] - 1] += 1
time[ex[0] - 1] = j
line = []
for h in range(n):
line.append([sum(score[h]), submit[h], time[h], h])
line.sort(key=lambda x: (-x[0], x[1], x[2]))
for rank in range(n):
if line[rank][3] == t - 1:
print(rank + 1)복잡도
- 시간: O(L + N log N)
- 공간: O(NK)