[ALGOSPOT] 알고스팟 MATCHORDER 출전 순서 정하기(C++, Python)

www.algospot.com

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

(C++, Python)

(글쓴날 : 2020.04.29)

 

---

* ALGOSPOT, 알고스팟 MATCHORDER 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

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

---

1) 문제

문제 링크 : https://www.algospot.com/judge/problem/read/MATCHORDER

algospot.com :: MATCHORDER

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

각각 다른 레이팅을 가지고 있는 N명의 러시아팀과 한국팀 선수들이 주어지고, 양 팀에서 한 명씩 나와 레이팅을 비교할 때, 한국팀이 레이팅이 높거나 같은 경우의 수를 구하는 문제입니다.

 

저의 경우, 그리디를 적용하였으며, C++과 Python을 사용했습니다.

먼저, 러시아팀을 내림차순, 한국팀을 오름차순으로 정렬하였고,

러시아팀은 첫 번째 인덱스부터, 한국팀은 마지막 인덱스부터 즉, 가장 높은 레이팅끼리 비교하여,

만약, 한국팀의 레이팅이 러시아팀보다 높거나 같을 시, 한국팀의 해당 레이팅 값을 제거하고 경우의 수를 1증가시키는 방식으로 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    vector<int> russia;
    vector<int> korea;
 
    int member = 0;
    int rating = 0;
    int compare = 0;
    int win = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> member;
 
        russia.clear();
        korea.clear();
        win = 0;
 
        for (int j = 0; j < member; j++)
        {
            cin >> rating;
            russia.push_back(rating);
        }
 
        for (int j = 0; j < member; j++)
        {
            cin >> rating;
            korea.push_back(rating);
        }
 
        sort(russia.begin(), russia.end(), greater<int>());
        sort(korea.begin(), korea.end());
 
        for (int i = 0; i < member; i++)
        {
            compare = russia[i];
 
            if (compare > korea.back())
                continue;
            else
            {
                korea.pop_back();
                win++;
            }
        }
 
        cout << win << "\n";
    }
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
 
for _ in range(N):
    member = int(input())
    russia = list(map(int, input().split()))
    korea = list(map(int, input().split()))
    win = 0
 
    russia.sort(reverse=True)
    korea.sort()
 
    for i in range(member):
        if russia[i] > korea[-1]:
            continue
        else:
            korea.pop()
            win += 1
 
    print(win)

---