[ 소프티어 ] 성적 평가 (C++)

https://softeer.ai/practice/6250

 

  참가자 N명의 점수를 내림차순으로 정렬하고, 각 참가자의 등수를 가능한 작게 부여하여 출력해야 하고, N의 크기가 최대 100000이므로 최대 n log n의 시간복잡도를 갖는 알고리즘으로 구현해야 한다.

 

[ 풀이 방법 ]

 각 참가자의 등수를 가능한 작게 부여하는 기능은 점수를 내림차순으로 정렬한 배열에서 참가자의 점수보다 같거나 작은 점수가 처음으로 등장한 인덱스를 찾는 것과 같다.

 처음엔 STL의 lower_bound()를 사용하여 구현하려 하였으나, 특정 원소보다 크거나 같은 원소의 첫 인덱스를 찾는 함수이기 때문에 오름차순으로 정렬된 컨테이너에서만 올바르게 작동하여 이 문제에서는 사용할 수 없었다.

 

 따라서 이분탐색을 이용해 내림차순으로 정렬된 컨테이너에서 특정 원소보다 작거나 같은 원소의 첫 인덱스를 찾는 기능을 직접 구현하여 문제를 해결할 수 있었다.

 

[ 정답 코드 ]

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

using namespace std;

int N;

int main(int argc, char** argv)
{
    iostream::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    vector<vector<int>> comp(3, vector<int>(N));
    vector<int> sum(N);

    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < N; j++) {
            cin >> comp[i][j];
            sum[j] += comp[i][j];
        }
    }

    vector<vector<int>> aux(comp.begin(), comp.end());
    vector<int> sumAux(sum.begin(), sum.end());
    
    sort(comp[0].begin(), comp[0].end(), greater<>());
    sort(comp[1].begin(), comp[1].end(), greater<>());
    sort(comp[2].begin(), comp[2].end(), greater<>());
    sort(sum.begin(), sum.end(), greater<>());
    
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < N; j++) {
            int l = 0;
            int r = N-1;
            while(l <= r) {
                int mid = l - (l-r)/2;
            
                if(comp[i][mid] > aux[i][j]) {
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
            if(j != N-1) cout << l+1 << " ";
            else cout << l+1;
        }
        cout << '\n';
    }

    for(int i = 0; i < N; i++) {
            int l = 0;
            int r = N-1;
            while(l <= r) {
                int mid = l - (l-r)/2;
            
                if(sum[mid] > sumAux[i]) {
                    l = mid+1;
                } else {
                    r = mid-1;
                }
            }
            if(i != N-1) cout << l+1 << " ";
            else cout << l+1;
        }
        cout << '\n';
        
   return 0;
}