C++로 리더보드(Leaderboard) 클래스 설계하기

```html

게임이나 경쟁 서비스에서 리더보드(Leaderboard)는 필수적인 요소입니다. 이번 글에서는 C++로 리더보드 클래스를 설계하는 방법을 단계별로 살펴보겠습니다. 설계해야 할 리더보드 클래스는 다음과 같은 세 가지 기능을 제공해야 합니다.

addScore(playerId, score) – 주어진 플레이어의 현재 점수에 score를 더해 리더보드를 갱신합니다. 만약 해당 playerId를 가진 플레이어가 리더보드에 없다면, 주어진 점수로 새롭게 등록합니다.
top(K) – 상위 K명 플레이어의 점수 합계를 반환합니다.
reset(playerId) – 주어진 playerId에 해당하는 플레이어의 점수를 0으로 초기화합니다. 이 함수가 호출되기 전에 해당 플레이어는 반드시 리더보드에 추가되어 있다고 가정합니다.

리더보드는 처음에 비어 있는 상태로 시작합니다.

동작 예시

다음과 같은 순서로 연산을 수행한다고 가정해 봅시다.

Leaderboard leaderboard = new Leaderboard();
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)

문제 해결 접근 방법

이 문제는 우선순위 큐(priority queue)와 맵(map)을 함께 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

정수 쌍(pair<int,int>)을 저장하는 우선순위 큐 pq와, int형 키와 값을 저장하는 맵 m을 정의합니다. 생성자에서는 맵을 비우고, 큐에 남아 있는 요소가 있다면 모두 제거합니다.
addScore() 메서드
- playerId가 맵에 이미 존재하면 m[playerId] = m[playerId] + score로 점수를 누적합니다.
- (m[playerId], playerId) 쌍을 pq에 삽입합니다.
- 존재하지 않는다면 m[playerId] = score로 새로 설정합니다.
top() 메서드
- pair를 담는 벡터 temp를 만들고 sum을 0으로 초기화합니다.
- k가 0이 아닌 동안 반복합니다.
  - pq의 최상단 요소를 curr에 저장한 뒤 pq에서 제거합니다.
  - m[curr.second](플레이어의 실제 현재 점수)가 curr.first와 일치하는 경우에만 유효한 데이터입니다. 이때 k를 1 감소시키고, sum에 curr.first를 더한 후 curr을 temp에 보관합니다.
- 반복이 끝나면 temp에 보관해 둔 요소들을 다시 pq에 삽입하여 원래 상태를 복원합니다.
reset() 메서드
- m[playerId] = 0으로 설정합니다.

여기서 한 가지 중요한 점은, addScore가 호출될 때마다 큐에 새 항목이 계속 쌓이기 때문에 큐 안에는 오래된(만료된) 점수 정보가 섞여 있을 수 있다는 것입니다. 따라서 top()에서는 맵의 실제 점수와 큐 항목의 점수를 비교하여 유효한 항목만 계산에 포함하는 것입니다.

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;
}

입력

리더보드를 초기화한 뒤 main() 함수에서처럼 각 함수를 호출하며 다양한 결과를 확인할 수 있습니다.

출력

73
102

복잡도 분석

addScore(): 우선순위 큐에 한 번 삽입하므로 O(log N)의 시간 복잡도를 가집니다.
top(K): 최악의 경우 큐의 모든 항목을 확인해야 하므로 O(N log N)까지 걸릴 수 있습니다.
reset(): 맵의 값만 갱신하므로 O(1)로 매우 빠릅니다.

이처럼 우선순위 큐와 맵을 조합하면 점수 갱신과 상위 K명 조회를 효율적으로 처리할 수 있는 리더보드를 손쉽게 구현할 수 있습니다.