728x90
반응형

문제:

당신은 유명 프로그래밍 대회인 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이다. 

출력:

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

풀이방법:

 주어지는 로그 엔트리들을 팀 ID, 문제 번호대로 정리를 잘 하고, 주어진 조건에 따라서 정렬을 하면 되는 문제다. 따라서 입력을 받을 당시에 defaultdict을 사용하여 raw 데이터를 저장하고, 이 와 동시에 가장 큰 점수와 마지막 인덱스도 저장하도록 한다.

 raw 데이터들은 Counter를 통해 빈도를 계산하며 이를 통합하여 정렬하도록 한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import defaultdict, Counter
= int(input())
for _ in range(T):
    n, k, t, m = map(int, input().split())
    score = dict()
    for i in range(1, n+1):
        score[i] = defaultdict(int)
 
    elements = []
    last_index = defaultdict(int)
    for idx in range(m):
        i, j, s = map(int, input().split())
        elements.append(i)
        score[i][j] = max(score[i][j], s)
        last_index[i] = idx 
 
    element_count = Counter(elements)
 
    total_score = []
    for i in range(1, n+1):
        total_score.append((i, sum(score[i].values()), element_count[i], last_index[i]))
    
    total_score = sorted(total_score, key=lambda x: (-x[1], x[2], x[3]))
 
    answer = 0
    for i, _, _, _ in total_score:
        if i==t:
            break
        answer+=1
    print(answer+1)
cs

문제링크:

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

 

3758번: KCPC

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는

www.acmicpc.net

 
728x90
반응형

'Algorithm > Python' 카테고리의 다른 글

[BOJ] 19637. IF문 좀 대신 써줘  (0) 2023.07.28
[Programmers] Lv 2. 점 찍기  (0) 2023.07.27
[BOJ] 2607. 비슷한 단어  (0) 2023.07.26
[Programmers]Lv 2. 호텔 대실  (0) 2023.07.25
[BOJ] 1515. 수 이어 쓰기  (0) 2023.07.24

+ Recent posts