[Python] 백준 3758 KCPC

1. 문제 - 백준 3758 KCPC

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

 

💡알고리즘 - 정렬

기본적으로 정렬 문제인데, 고려해야할 사항이 아래와 같이 존재한다.

 

1) 한 문제에 대한 풀이를 여러번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다.

- 팀 별 문제 별 최고 점수를 기록해야한다.

 

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

- 정렬을 위해 팀 별 최종 점수, 풀이를 제출한 횟수, 마지막 제출 시간을 기록해야한다.

 

✅ 풀이

t = int(input())
for _ in range(t):
  # 팀의 갯수, 문제 갯수, 팀의 id, 로그의 갯수
  n, k, t, m = map(int, input().split())
  dic = {x: [0, 0, 0] for x in range(1, n+1)}
  score = {x: [0] * (k+1) for x in range(1, n+1)}
  
  for time in range(m):   # 제출 시간
    # 팀 id, 문제 번호, 획득한 점수
    i, j, s = map(int, input().split())
    dic[i][1] += 1
    dic[i][2] = time
    score[i][j] = max(score[i][j], s)

  for x in range(1, n+1):
    dic[x][0] = sum(score[x])

  result = sorted(dic.items(), key=lambda x:(-x[1][0], x[1][1], x[1][2]))
  for idx, arr in enumerate(result):
    if arr[0] == t:
      print(idx+1)

 

1) 한 문제에 대한 풀이를 여러번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다.

- 팀 별 문제 별 최고 점수를 기록해야하는데, key값을 팀 id로 하고 value가 문제별 최고 점수인 리스트인 score 딕셔너리를 만든다.

- 리스트는 문제 갯수인 k가 주어지므로 [0] * (k+1) 로 초기화한다. (k+1인 이유는 인덱스가 0부터 시작하니까 문제 번호가 1부터 시작하는 부분을 대응하기 위함)

 

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

- 이후 정렬을 쉽게 하기 위해 key값을 팀 id로 하고 첫번째가 최종 점수, 두번째가 풀이를 제출한 횟수, 세번째가 마지막 제출 시간인 리스트가 value인 dic 딕셔너리를 만든다.

 

이후 m번만큼 문제를 입력받을때마다 팀 id별로 (딕셔너리의 key) 풀이를 제출한 횟수, 제출 시간, 문제 별 최대값을 각각 기록한다.

이후 팀 별 최종 점수를 합산한 다음, 최종점수 내림차순 -> 제출한 횟수 오름차순 -> 제출시간 오름차순 순으로 정렬한다.

  result = sorted(dic.items(), key=lambda x:(-x[1][0], x[1][1], x[1][2]))

 

💡 새로 알게된 내용

정렬 문제를 풀때, 데이터를 어떻게 저장할지를 먼저 기록해보자. key가 정수일 경우, 리스트의 인덱스를 활용하는 경우도 같이 고려하자.