[백준 3758 🥈] KCPC

문제

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 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이다. 

출력

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

문제 풀이

• 각 팀 별로 총 점수, 제출 횟수, 제출 시간을 계산하는 것은 단순 구현으로 풀어주면 된다.
  • 제출 횟수와 제출 시간은 team_info에 저장된 각 팀의 정보를 각각 +1해주고, 새로운 제출시간으로 갱신해주면 되고, 각 문제에 대해선 더 높은 점수가 최종 점수이므로 새로운 점수가 더 높다면 기존의 해당 문제의 점수를 총 점수에서 빼준 뒤에, 새로운 점수를 더해준다.
  • 그리고 각 문제당 점수엔 새로운 점수를 저장해주면 된다. 
• 순위를 출력하는 것은 총 점수 내림차순, 제출 횟수 오름차순, 제출 시간 오름차순으로 정렬해서 우리 팀의 순위를 찾으면 된다.
• 하지만, 처음에 나는 순위를 찾는 것을 정렬하지 않고, 그냥 우리 팀의 총 점수, 제출 횟수, 제출 시간을 저장해놓고, 우리 팀보다 총 점수가 높은 팀을 찾으면 +1, 총 점수는 같지만 제출 횟수가 더 적은 팀을 찾으면 +1, 총 점수와 제출 횟수는 같지만 제출 시간이 더 빠른 팀을 찾으면 +1 하는 방식으로 순위를 찾아서 출력했고, 이 방식도 통과를 받긴 했다!
• 그래도 이 문제의 알고리즘 분류가 정렬로 되어 있는 것을 보고, 정렬을 사용해서 다시 제출했다.
  
  • 여기서 sort()를 할 때, key 값으로 여러 값을 정렬 기준으로 줄 수 있는데, 아래 예시처럼 내림차순으로 정렬하고 싶을 땐 -를 붙여주면 된다. 

team_info=[0,0,0,[0]*(k)]*n

• 여기서 주의할 점은, 처음에 [0,0,0,[0]*k] 형태의 배열은 팀의 개수만큼 선언해주기 위해 아래와 같은 list comprehension이 아니라 위와 같이 *을 이용한 복사 형태로 선언했었다.
• 이러면 각 배열의 참조값들도 함께 복사되어 team_info[1][0]=1을 저장해주면 team_info[0][0], team_info[2][0]까지 모두 1로 저장되는 현상이 일어났다. 구글링해보니 아래와 같은 글을 찾을 수 있었다!
• https://sogogi1000inbun.tistory.com/33

[python] 2차원 리스트를 생성하고 요소 변경하는 차이

team_info=[[0,0,0,[0]*(k),t_id] for t_id in range(n)]

• 결론 : 위와 같은 경우, list comprehension을 사용하자

import sys

t=int(sys.stdin.readline())
for _ in range(t):
    n,k,t,m=map(int, sys.stdin.readline().split(' '))
    # n개의 팀에 대한 정보 배열
    # 총 점수, 제출횟수, 제출시간, 문제번호별 점수
    team_info=[[0,0,0,[0]*(k),t_id] for t_id in range(n)]
    for time in range(m):
        team, pnum, score = map(int, sys.stdin.readline().split(' '))
        # 제출 횟수, 제출 시간 갱신
        team_info[team - 1][1] += 1
        team_info[team-1][2] = time
        # 해당 문제의 현재 점수보다 새로운 점수가 더 높다면, 점수 갱신
        if team_info[team-1][3][pnum-1]<score:
            team_info[team-1][0]-=team_info[team-1][3][pnum-1]
            team_info[team-1][0]+=score
            team_info[team-1][3][pnum-1]=score

    team_info.sort(key=lambda x:(-x[0], x[1], x[2]))
    for rank in range(n):
        if team_info[rank][4]==t-1:
            print(rank+1)
            break
            
    # 직접 구현
    # mscore,mnum,mtime,mpros =team_info[t-1]
    # ans=1
    # for idx in range(n):
    #     if idx==t-1:
    #         continue
    #     ts, tm, tt, tp=team_info[idx]
    #     # 우리팀 점수보다 높은 점수일 경우
    #     if ts>mscore:
    #         ans+=1
    #     # 우리팀 점수와 동일하다면, 제출 횟수가 더 적은지 확인
    #     elif ts==mscore:
    #         if tm<mnum:
    #             ans+=1
    #         elif tm==mnum:
    #             # 제출 횟수가 동일하다면, 최종 제출 시간이 더 빠른지 확인
    #             if tt<mtime:
    #                 ans+=1
    # print(ans)