N명의 선수들의 점수 목록이 주어졌을 때, 각 선수의 상대 순위를 구하는 문제입니다. 이때 가장 높은 점수를 기록한 상위 세 명의 선수에게는 각각 "Gold"(금메달), "Silver"(은메달), "Bronze"(동메달)가 부여되며, 나머지 선수들은 자신의 등수를 문자열 형태로 받게 됩니다.
예를 들어 입력이 [2,5,3,1,0]이라면 출력은 [Bronze, Gold, Silver, 4, 5]가 됩니다. 즉, 5점이 금메달, 3점이 은메달, 2점이 동메달을 차지하고, 1점과 0점을 기록한 선수는 각각 4위, 5위가 됩니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
nums의 크기가 1이라면 "Gold"를 그대로 반환합니다.
nums의 크기가 2라면 다음과 같이 처리합니다.
nums[0] > nums[1]이면 ["Gold", "Silver"]를 반환합니다.
그렇지 않으면 ["Silver", "Gold"]를 반환합니다.
정수 배열 v와 문자열 배열 vec을 정의합니다.
i := 0부터 i < nums.size()까지 반복하면서 v의 끝에 nums[i]를 추가합니다.
배열 v를 오름차순으로 정렬한 뒤, 역순으로 뒤집어 내림차순으로 만듭니다.
맵 mp를 하나 정의합니다.
nums의 크기가 2보다 큰 경우 다음을 수행합니다.
mp에 {v[0], "Gold"}, {v[1], "Silver"}, {v[2], "Bronze"}를 삽입합니다.
i := 3부터 i < v.size()까지 반복하면서 mp에 {v[i], to_string(i + 1)}을 삽입하여 4위부터의 등수를 매핑합니다.
i := 0부터 i < nums.size()까지 반복하면서 vec의 끝에 mp[nums[i]]를 추가합니다.
최종 결과 vec을 반환합니다.
예제 코드
아래의 C++ 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> findRelativeRanks(vector<int>& nums){
if (nums.size() == 1){
return { "Gold" };
}
if (nums.size() == 2){
if (nums[0] > nums[1])
return { "Gold", "Silver" };
else
return { "Silver", "Gold" };
}
vector<int> v;
vector<string> vec;
for (int i = 0; i < nums.size(); i++)
v.push_back(nums[i]);
sort(v.begin(), v.end());
reverse(v.begin(), v.end());
map<int, string> mp;
if (nums.size() > 2) {
mp.insert({v[0], "Gold" });
mp.insert({v[1], "Silver" });
mp.insert({v[2], "Bronze" });
for (int i = 3; i < v.size(); i++) {
mp.insert({ v[i], to_string(i + 1) });
}
for (int i = 0; i < nums.size(); i++)
vec.push_back(mp[nums[i]]);
}
return vec;
}
};
main(){
Solution ob;
vector<int> v = {2,5,3,1,0};
print_vector(ob.findRelativeRanks(v));
}
입력
{2,5,3,1,0}
출력
[Bronze, Gold, Silver, 4, 5]
복잡도 분석
점수 배열을 정렬하는 데 O(n log n)의 시간이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 또한 정렬된 배열과 맵을 저장하기 위해 O(n)의 추가 공간이 필요합니다. 이 알고리즘은 정렬과 맵을 활용해 각 선수의 원래 위치를 유지하면서도 빠르게 순위를 매핑할 수 있다는 장점이 있습니다.