Level 0. 등수 매기기

Level 0. 등수 매기기

 

 

평균 점수를 저장하는 벡터1, 역순 정렬된 상태로 저장하는 벡터2를 만들어 해결하였다.

 

시작 주소부터 원소까지의 거리에 1을 더하면 등수가 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> solution(vector<vector<int>> score)
{
    vector<int> answer;
    vector<float> vec1, vec2;

    for (const vector<int>& v : score)
        vec1.emplace_back((v[0] + v[1]) * 0.5);

    vec2 = vec1;
    sort(vec2.rbegin(), vec2.rend());

    for (const float& average : vec1)
        answer.emplace_back(find(vec2.begin(), vec2.end(), average) - vec2.begin() + 1);

    return answer;
}

 

알고리즘을 풀 때 항상 느끼는 것이 있다.

문제를 풀고 내 풀이가 가장 좋지 않을까라는 기대를 품으며 다른 사람의 풀이를 보면 항상 더 좋은 풀이가 있다..

 

평균이라고는 하지만 비교를 위해서는 굳이 나누지 않고 합을 그대로 사용해도 된다.

 

벡터의 크기를 필요한 만큼 미리 만들어 주어 내부적으로 메모리 재할당이 일어나지 않도록 했다.

 

원소들을 정렬하지 않고도 자신보다 큰 원소의 개수를 계산하여 해결했다.

 

마지막 부분의 시간 복잡도는 O(n²)으로 동일하지만 좀 더 간단한 방법이라고 생각한다.

 

#include <iostream>
#include <vector>

using namespace std;

vector<int> solution(vector<vector<int>> score)
{
    vector<int> answer(score.size());
    vector<int> vec(score.size());
    vector<int>::iterator vec_it = vec.begin(), answer_it = answer.begin();
    
    for (vector<int>& v : score)
        *(vec_it++) = v[0] + v[1];
    
    for (const int& e1 : vec)
    {
        int count = 0;

        for (const int& e2 : vec)
            count += (e1 < e2);

        *(answer_it++) = ++count;
    }

    return answer;
}