리더보드 클래스를 디자인해야 한다고 가정하면 세 가지 다른 기능이 있습니다. −
- addScore(playerId, score) - 주어진 플레이어의 점수에 점수를 추가하여 리더보드를 업데이트합니다. 리더보드에 주어진 ID를 가진 플레이어가 없을 경우, 주어진 점수로 리더보드에 추가합니다.
- top(K) - 상위 K 플레이어의 점수 합계를 반환합니다.
- reset(playerId) - 주어진 ID를 가진 플레이어의 점수를 0으로 재설정합니다. 이 함수를 호출하기 전에 플레이어가 리더보드에 추가되었음을 보장합니다.
처음에는 리더보드가 비어 있어야 합니다.
아래와 같은 작업을 수행하면 -
- 리더보드 리더보드 =새로운 리더보드();
- leaderboard.addScore(1,73); // 리더보드는 [[1,73]];
- leaderboard.addScore(2,56); // 리더보드는 [[1,73],[2,56]];
- leaderboard.addScore(3,39); // 리더보드는 [[1,73],[2,56],[3,39]];
- leaderboard.addScore(4,51); // 리더보드는 [[1,73],[2,56],[3,39],[4,51]];
- leaderboard.addScore(5,4); // 리더보드는 [[1,73],[2,56],[3,39],[4,51],[5,4]];
- leaderboard.top(1); // 73을 반환합니다.
- leaderboard.reset(1); // 리더보드는 [[2,56],[3,39],[4,51],[5,4]];
- leaderboard.reset(2); // 리더보드는 [[3,39],[4,51],[5,4]];
- leaderboard.addScore(2,51); // 리더보드는 [[2,51],[3,39],[4,51],[5,4]];
- leaderboard.top(3); // 141 =51 + 51 + 39를 반환합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- pq라는 정수 쌍의 우선 순위 대기열을 정의하고 int 유형 키와 int 유형 값 m의 하나의 맵을 만듭니다. 초기화를 위해 맵을 지우고 큐가 비어 있지 않으면 큐에서 모든 요소를 삭제합니다.
- addScore() 메서드는 다음과 같습니다. -
- playerId가 있는 경우 m[playerId] :=m[playerId] + 점수
- pq에 쌍(m[playerId], playerId) 삽입
- 그렇지 않으면 m[playerId] =점수
- top() 메서드는 다음과 같습니다.
- temp 쌍의 벡터를 만들고 합계를 0으로 설정
- k가 0이 아닌 동안
- curr :=pq의 상단, pq에서 삭제
- m[통화 쌍의 두 번째 값] =통화 쌍의 첫 번째 값인 경우
- k를 1 감소
- sum :=sum + curr의 첫 번째 값
- 온도에 curr 삽입
- 0에서 temp 크기까지의 i에 대해
- pq에 temp[i] 삽입
- reset() 함수는 다음과 같습니다 -
- m[playerId] =0
예(C++)
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Leaderboard {
public:
priority_queue< pair <int,int> > pq;
map < int, int > m;
Leaderboard() {
m.clear();
while(!pq.empty())pq.pop();
}
void addScore(int playerId, int score) {
if(m.find(playerId)!=m.end()){
m[playerId] += score;
}
else m[playerId] = score;;
pq.push({m[playerId], playerId});
}
int top(int k) {
vector < pair <int,int> > temp;
int sum = 0;
while(k){
pair <int, int> curr = pq.top();
pq.pop();
if(m[curr.second] == curr.first){
k--;
sum += curr.first;
temp.push_back(curr);
}
}
for(int i = 0; i < temp.size(); i++)pq.push(temp[i]);
return sum;
}
void reset(int playerId) {
m[playerId] = 0;
}
};
main(){
Leaderboard ob;
ob.addScore(1,73);
ob.addScore(2,56);
ob.addScore(3,39);
ob.addScore(4,51);
ob.addScore(5,4);
cout <<ob.top(1) << endl;
ob.reset(1);
ob.reset(2);
ob.addScore(2,51);
cout <<ob.top(2) << endl;
} 입력
Initialize leader board then use the functions to see different results. See the main() function
출력
73 102