[알고리즘] 백준 3758번: KCPC

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

3758번: KCPC

 

📝 문제

이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다.
풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다.
한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다.
(만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)
당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다.
점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다.

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다.
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라.
서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

 

⌨️ 입력

입력 데이터는 표준 입력을 사용한다.
입력은 T개의 테스트 데이터로 구성된다.
입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다.
각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다.
여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다.
각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다.
여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다.

 

🖥️ 출력

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

 

💡 아이디어

필요한거
제출 횟수, 마지막 제출, 팀별 점수 총합
딕셔너리 밸류 정렬을 다시 해야 할 때가 온건가...

 

🧑🏻‍💻 Code

def solve():
    n, k, t, m = map(int, input().split())
    scores_arr = [[0 for _ in range(k+1)] for _ in range(n+1)]
    cnt_d = {}
    last_d = {}
    for submit in range(m):
        i, j, s = map(int, input().split())
        if scores_arr[i][j] < s:
            scores_arr[i][j] = s
        if i in cnt_d:
            cnt_d[i] += 1
        else:
            cnt_d[i] = 1
        last_d[i] = submit
    res = sorted(cnt_d.items(), key=lambda x: (-sum(scores_arr[x[0]]), x[1], last_d[x[0]]))
    ranking = 1
    for team in res:
        if team[0] == t:
            print(ranking)
            return
        ranking += 1

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solve()

💬 소감

으아 시간 터진다 으아아
리팩토링 해야겠다 으아아

 

+ 이것도 15일에 제출하고 커밋도 했지롱