ALGOSPOT MATCHORDER 알고스팟 출전 순서 정하기

ALGOSPOT MATCHORDER 알고스팟 출전 순서 정하기

include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include <algorithm>
using namespace std;
 
int N;
//선수가 출전했는지 안했는지 여부
//1이면 출전함,0이면 출전안한 선수
bool visited[4001];
 
int Winner(vector<int> Russia, vector<int> korea) {
    int Winnum = 0;
 
    for (int i = 0; i < N; i++) {
        int low = 0;
        int high = N - 1;
        for (int k = N - 1; k >= 0; k--) {
            if (!visited[k]) {
                break;
            }
            high--;
        }
        for (int j = 0; j < N; j++) {
            if (!visited[j]) {
                break;
            }
            low++;
        }
        if (low == N) return Winnum;
        if (high == -1) return Winnum;
        if (Russia[i] > korea[high]) {
            visited[low] = true;
        }
        else {
            while ((Russia[i] > korea[low]) || visited[low]) {
                low++;
            }
            visited[low] = true;
            Winnum++;
        }
    }
    return Winnum;
 
}
int main(void) {
    int cases;
    cin >> cases;
    while (cases--) {
        memset(visited, 0, sizeof(visited));
        cin >> N;
        vector<int> Russia(N);
        vector<int> korea(N);
        for (int i = 0; i < N; i++)
            cin >> Russia[i];
 
        for (int i = 0; i < N; i++)
            cin >> korea[i];
        sort(korea.begin(), korea.end());
        cout<<Winner(Russia, korea)<<endl;
        
    }
    return 0;
}

이 코드는 책의 문제답안을 보기전 작성한 코드이다.

#include<iostream>
#include<vector>
#include<string>
#include<cstring>
#include <algorithm>
#include<set>
using namespace std;
 
int N;
 
int Winner(const vector<int>& russian, const vector<int> & korean) {
    int n = russian.size(), wins = 0;
    //아직 남아 있는 선수들의 레이팅
    multiset<int> ratings(korean.begin(), korean.end());
    for (int rus = 0; rus < n; rus++) {
        //가장 레이팅이 높은 한국 선수가 이길 수 없는 경우
        //가장 레이팅이 낮은 선수와 경기시킨다.
        if (*ratings.rbegin() < russian[rus])
            ratings.erase(ratings.begin());
        //이 외의 경우 이길 수 있는 선수 중 가장 레이팅이 낮은 선수와 경기시킨다.
        else {
            ratings.erase(ratings.lower_bound(russian[rus]));
            wins++;
        }
    }
    return wins;
}
 
int main(void) {
    int cases;
    cin >> cases;
    while (cases--) {
        cin >> N;
        vector<int> Russia(N);
        vector<int> korea(N);
        for (int i = 0; i < N; i++)
            cin >> Russia[i];
 
        for (int i = 0; i < N; i++)
            cin >> korea[i];
        cout<<Winner(Russia, korea)<<endl;
        
    }
    return 0;
}

문제 출처:https://algospot.com/judge/problem/read/MATCHORDER

난이도는 쉬운 문제지만 처음보는 함수를 사용하네요 multiset<int> 활용하는 법을 익히면 좋을 것 같습니다.

따로 sort함수를 사용해서 vector korea를 정렬시키지 않았음에도 문제없이 잘 돌아가네요.