문제
당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)
당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다.
점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다.
- 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다.
- 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다.
동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라.
서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.
입력
입력 데이터는 표준 입력을 사용한다. 입력은 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이다.
출력
출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다
예제 입력
2
3 4 3 5
1 1 30
2 3 30
1 2 40
1 2 20
3 1 70
4 4 1 10
1 1 50
2 1 20
1 1 80
3 1 0
1 2 20
2 2 10
4 3 0
2 1 0
2 2 100
1 4 20예제 출력
1
2Code
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split('\n');
let T = +input[0]; // 테스트케이스 개수
let line = 1;
let answer = '';
while (T > 0) {
// n: 팀의 개수, k: 문제의 개수, t: 내 팀의 ID, m: 로그 엔트리 개수
const [n, k, t, m] = input[line].split(' ').map(Number);
const teamAnswer = Array.from({ length: n + 1 }, () => new Map()); // 각 팀 별 문제 당 최고 점수 저장
const teamInfo = Array.from({ length: n + 1 }).map((_, idx) => [
idx,
0,
0,
0,
]); // 팀 번호, 최종점수, 로그 횟수, 최근 남긴 로그 시간
for (let info = line + 1; info <= line + m; info += 1) {
// i: 팀 ID, j: 문제 번호, s: 획득 점수
const [i, j, s] = input[info].split(' ').map(Number);
teamInfo[i][2] += 1; // 로그 횟수 추가
teamInfo[i][3] = info; // 최근 남긴 로그 시간 업데이트
// 각 팀의 각 문제의 점수 변경
if (!teamAnswer[i].has(j))
teamAnswer[i].set(j, s); // 처음 푼 문제인 경우
else {
if (teamAnswer[i].get(j) < s) teamAnswer[i].set(j, s); // 새로 푼 문제의 점수가 더 높을 경우 변경
}
}
// 각 팀 별 최종 점수 넣기
teamAnswer.forEach((team, index) =>
team.forEach((score) => (teamInfo[index][1] += score))
);
// 최종 점수 기준으로 내림차순 정렬 || 최종 점수 같다면 로그 횟수 기준으로 오름차순 정렬(적은 기준) || 둘 다 같다면 로그 시간 오름차순 정렬(오래된 시간 기준)
teamInfo
.sort((a, b) => b[1] - a[1] || a[2] - b[2] || a[3] - b[3])
.forEach((team, idx) => {
if (team[0] === t) answer += idx + 1 + '\n';
});
line += m + 1;
T -= 1;
}
answer = answer.trimEnd();
console.log(answer);풀이 및 해설
- n개의 팀 별로 해시 배열 만들기 ⇒ 푼 문제 별로 점수 체크하기 위해서
- 이미 푼 문제를 새로 푼 경우 점수가 더 높을 때만 업데이트
- 최종적으로 각 팀 별 최종 점수 정렬을 수행할 배열에 넣기
- [팀 ID, 최종 점수, 로그 횟수, 마지막 로그 시간]을 기준으로 정렬 수행
- 최종 점수 기준으로 내림차순 정렬 ⇒ 최종 점수가 높은 기준
- 최종 점수가 같다면 로그 횟수 기준으로 오름차순 정렬 ⇒ 로그 횟수가 가장 적은 기준
- 둘 다 같다면 마지막 로그 시간 기준으로 오름차순 정렬 ⇒ 가장 오래된 로그 시간 기준
- t(내 팀 ID)에 맞는 인덱스 찾아서 등수 출력
