[hacker rank] Climbing the leaderboard

문제 링크

 

풀이

쉽게 풀면 시간 복잡도가 O(N^2)으로 나오는데 실행 시간 초과로 통과되기 어려울 것입니다. 주어진 ranked 배열은 내림차순으로 정렬 되어 있고 player 배열은 오름차순입니다. 따라서 player 배열의 마지막부터 올라가면서 점수 별 player의 순위를 구하면 player 배열은 1번만 순회해도 되기 때문에 O(N)으로 문제를 풀 수 있습니다. 구하는 순위는 상승하기만 하므로 매번 처음부터 새로 구할 필요가 없기 때문입니다.

 

코드1

vector<int> climbingLeaderboard(vector<int> ranked, vector<int> player) {
    int N = ranked.size();
    int M = player.size();
    int my_rank = 1;
    for (size_t i = 0; i < ranked.size() - 1; ++i)
        if (ranked[i] > ranked[i + 1])
            ++my_rank;
    vector<int> answer;
    answer.reserve(M);
    my_rank += 1;
    size_t r_index = ranked.size() - 1;
    for (size_t i = 0; i < M; ++i)
    {
        auto my_score = player[i];
        while (my_score >= ranked[r_index])
        {
            if (0 == r_index)
            {
                my_rank = 1;
                break;
            }
            if (ranked[r_index] != ranked[r_index - 1])
            {
                --my_rank;
                --r_index;
            }
            else
                --r_index;
        }
        answer.push_back(my_rank);
    }
    return answer;
}

 

코드2(반복문 하나만 사용)

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> climbingLeaderboard(vector<int> ranked, vector<int> player)
{
	int my_rank = 1;
	for (size_t i = 0; i < ranked.size() - 1; ++i)
	{
		if (ranked[i] > ranked[i + 1])
			++my_rank;
	}
	++my_rank;
	int r_idx = ranked.size() - 1;
	int p_idx = 0;
	vector<int> answer;
	int size = player.size();
	answer.reserve(size);
	while (p_idx + 1 <= size)
	{
		auto me = player[p_idx];
		auto rank = ranked[r_idx];
		if (me >= rank)
		{
			if (r_idx == 0)
			{
				answer.push_back(1);
				++p_idx;
			}
			else if (ranked[r_idx - 1] != ranked[r_idx])
			{
				--my_rank;
				--r_idx;
			}
			else
				--r_idx;
		}
		else
		{
			answer.push_back(my_rank);
			++p_idx;
		}
	}
	return answer;
}