[HackerRank] Climbing the Leaderboard

HackerRank 알고리즘 문제 풀이

분류

Practice > Algorithms > Implementation

문제 링크 : https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

풀이

Rank와 Score 정보를 함께 갖는 Data 타입의 벡터를 선언하고, 이분 탐색을 위해 score를 기준으로 오름차순 정렬하였다.

이분탐색을 직접 구현해도 되지만 lower_bound 함수를 사용했다.

• lower_bound 함수는 찾으려는 값과 같거나 더 큰 위치를 반환한다.

한 가지 주의할 점은 임의의 유저 스코어 값 p가 vector<Data> dat에 들어있는 score값보다 크다면, lower_bound 함수는 dat.end()(벡터의 끝)을 반환한다. 벡터의 끝을 가리키고 있을 때는 해당 데이터의 필드(여기서는 score, rank)에 접근할 수 없으므로 에러가 발생하지 않게 주의한다. 나는 아래와 같이 예외처리를 해두었다.

if (pos == dat.end()) { // lower_bound의 반환값을 받는 pos가 벡터(dat)의 end 위치인 경우
    // ans.push_back((pos - 1)->rank);
    ans.push_back(1); // 가장 큰 점수일 때 end 위치이고, 가장 큰 점수일 때의 순위는 1위다.
    continue;
}

소스 코드

#include <bits/stdc++.h>

using namespace std;

string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);

/*
 * Complete the 'climbingLeaderboard' function below.
 *
 * The function is expected to return an INTEGER_ARRAY.
 * The function accepts following parameters:
 *  1. INTEGER_ARRAY ranked
 *  2. INTEGER_ARRAY player
 */

struct Data {
    int score;
    int rank;
};
vector<int> climbingLeaderboard(vector<int> ranked, vector<int> player) {
    vector<int> ans;
    vector<Data> dat;
    int r = 1;
    dat.push_back({ ranked[0], r });
    for (int i = 1; i < (int)ranked.size(); ++i) {
        if (dat.back().score == ranked[i]) continue;
        dat.push_back({ ranked[i], ++r });
    }

    sort(dat.begin(), dat.end(), [](const Data& A, const Data& B) {
        return A.score < B.score;
    });

    for (int p : player) {
        const auto& pos = lower_bound(dat.begin(), dat.end(), p, [](const Data& A, int score) {
            return A.score < score;
        });

        if (pos == dat.end()) {
            ans.push_back((pos - 1)->rank);
            continue;
        }

        if (p < pos->score) {
            ans.push_back(pos->rank + 1);
        }
        else {
            ans.push_back(pos->rank);
        }
    }

    return ans;
}

int main()
{
    string ranked_count_temp;
    getline(cin, ranked_count_temp);

    int ranked_count = stoi(ltrim(rtrim(ranked_count_temp)));

    string ranked_temp_temp;
    getline(cin, ranked_temp_temp);

    vector<string> ranked_temp = split(rtrim(ranked_temp_temp));

    vector<int> ranked(ranked_count);

    for (int i = 0; i < ranked_count; i++) {
        int ranked_item = stoi(ranked_temp[i]);

        ranked[i] = ranked_item;
    }

    string player_count_temp;
    getline(cin, player_count_temp);

    int player_count = stoi(ltrim(rtrim(player_count_temp)));

    string player_temp_temp;
    getline(cin, player_temp_temp);

    vector<string> player_temp = split(rtrim(player_temp_temp));

    vector<int> player(player_count);

    for (int i = 0; i < player_count; i++) {
        int player_item = stoi(player_temp[i]);

        player[i] = player_item;
    }

    vector<int> result = climbingLeaderboard(ranked, player);

    for (int i = 0; i < result.size(); i++) {
        cout << result[i];

        if (i != result.size() - 1) {
            cout << "\n";
        }
    }

    cout << "\n";

    return 0;
}

string ltrim(const string &str) {
    string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );

    return s;
}

string rtrim(const string &str) {
    string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );

    return s;
}

vector<string> split(const string &str) {
    vector<string> tokens;

    string::size_type start = 0;
    string::size_type end = 0;

    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));

        start = end + 1;
    }

    tokens.push_back(str.substr(start));

    return tokens;
}