안 주면 훔칩니다 안 주면 훔칩니다

Medium

• [hacker rank] Climbing the leaderboard

  알고리즘/Hacker Rank 2021. 9. 4. 13:49

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

  Read More