상대 순위 Leetcode 솔루션

난이도 쉽게
자주 묻는 질문 구글
알고리즘 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 정렬조회수 30

문제 Relative Ranks Leetcode Solution은 상대 순위를 나타내는 벡터 또는 문자열 배열을 반환하도록 요청합니다. 우리는 정렬 선수가 얻은 점수를 나타냅니다. 그런 다음 주어진 점수 배열을 사용하여 순위를 할당합니다. 상위 3 명의 후보자에게는 약간의 변화가 있습니다. 대신에 간단한 숫자 1, 2 또는 3을 할당합니다. 금,은, 동메달을 할당해야합니다. 상위 3 개 후보 외에 4부터 n까지 간단한 숫자를 할당 할 수 있습니다. 몇 가지 예를 살펴 보겠습니다.

상대 순위 Leetcode 솔루션

[1, 2, 3]
["Bronze Medal", "Silver Medal", "Gold Medal"]

설명 : 주어진 배열은 선수들이 얻은 점수를 나타 내기 때문입니다. 가장 높은 점수를받은 선수는 금메달 등을 받게됩니다. 따라서 우리는 3 점의 선수에게 금메달, 2 점의 선수에게 은메달, 1 점의 선수에게 동메달을주었습니다.

[5, 4, 3, 2, 1]
["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]

설명 : 상위 3 명의 후보에게는 메달이 수여되고 나머지 후보에게는 순위가 지정됩니다. 따라서 우리는 상위 3 명의 후보자에게 메달을 할당하고 해당 후보자에게 순위 4, 5를 할당했습니다.

접근

Relative Ranks Leetcode Solution 문제는 상위 3 명의 후보에게 메달을 할당하고 나머지 후보에게 순위를 할당하도록 요청합니다. 생각할 수있는 가장 간단한 것은 주어진 시퀀스를 정렬하는 것입니다. 하지만 원래 인덱스에 순위를 할당해야합니다. 따라서 주어진 시퀀스를 직접 정렬하면 원래 인덱스가 누락됩니다. 그리고 순위 할당을 결정할 수 없습니다. 따라서 원래 인덱스를 잃지 않도록하기 위해 점수와 함께 원래 인덱스를 저장하는 새 벡터 또는 배열을 만듭니다. 이 새로운 배열이나 벡터를 정렬합니다. 정렬 후 금메달, 은메달, 동메달을 해당 후보자에게 할당하고 자격이있는 후보자에게 4부터 n까지 순위를 매 깁니다. 새로 수정 된 배열이나 벡터를 정렬 할 때 원래 인덱스도 저장된 값에 해당하는 위치를 바꾸기 때문에 이렇게 할 수 있습니다.

상대 순위에 대한 코드 Leetcode 솔루션

상대 순위 Leetcode 솔루션을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

vector<string> findRelativeRanks(vector<int>& nums) {
    vector<pair<int,int>> temp;
    int n = nums.size();
    for(int i=0;i<n;i++){
        temp.push_back(make_pair(nums[i], i));
    }
    sort(temp.rbegin(), temp.rend());
    vector<string> answer(n);
    answer[temp[0].second] = "Gold Medal";
    if(n>=2){
        answer[temp[1].second] = "Silver Medal";
    }
    if(n>=3){
        answer[temp[2].second] = "Bronze Medal";
    }
    for(int i=3;i<n;i++)
        answer[temp[i].second] = to_string(i+1);
    return answer;
}

int main(){
    vector<int> nums = {5, 4, 3, 2, 1};
    vector<string> answer = findRelativeRanks(nums);
    for(auto x: answer)cout<<x<<" ";
}
Gold Medal Silver Medal Bronze Medal 4 5

자바 코드 상대 순위 Leetcode 솔루션

import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {
  
    public static String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[][] pair = new int[nums.length][2];
        for (int i = 0; i < n; i++) {
            pair[i][0] = nums[i];
            pair[i][1] = i;
        }
        
        Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
        
        String[] result = new String[nums.length];
        result[pair[0][1]] = "Gold Medal";
        if(n>=2)
            result[pair[1][1]] = "Silver Medal";
        if(n>=3)
            result[pair[2][1]] = "Bronze Medal";
        for (int i = 3; i < nums.length; i++) {
            result[pair[i][1]] = Integer.toString(i+1);
        }

        return result;
    }
    
  public static void main (String[] args) throws java.lang.Exception{
    int[] nums = {5, 4, 3, 2, 1};
    String[] answer = findRelativeRanks(nums);
    for(int i=0;i<5;i++)
      System.out.print(answer[i] + " ");
  }
}
Gold Medal Silver Medal Bronze Medal 4 5

복잡성 분석

시간 복잡성

O (NlogN), 정렬에는 O (NlogN) 시간이 필요하기 때문입니다. 여기서 N은 정렬되는 벡터 또는 배열의 요소 수입니다.

공간 복잡성

O (NlogN), O (NlogN) 공간을 차지하는 정렬을 사용했기 때문입니다. 공간 복잡도는 시간 복잡도와 동일합니다.

코멘트를 남겨

Translate »
1