[프로그래머스 lv3] 숫자 게임 풀이

✅ 프로그래머스의 모든 문제와 해설 보기[클릭]

 

해설

A의 출전 순서를 알고 있으므로 원하는대로 A 선수와 B 선수를 매칭시킬 수 있다.

B의 승리 횟수를 최대화 하기 위해서는 A의 작은 수들부터 차례로 이겨나가야 한다.

A의 여러가지 수들 중에서 작은 수를 이기는 것이 큰 수를 이기는 것보다 가성비가 좋기 때문이다. 

 

따라서, A와 B를 오름차순으로 정렬한 뒤 A[i]를 이길 수 있는 B의 원소를 탐색한다.

A[i]를 이길 수 있는 B의 원소가 존재할 때 nwin을 1 증가시키고 최종 nwin 값을 리턴하면 정답이다.

 

 

코드

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <tuple>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <iostream>

using namespace std;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define X first
#define Y second

int solution(vector<int> A, vector<int> B) {

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    int idx = 0, nwin = 0;
    for (int i=0; i<(int)A.size(); i++) {
        while (idx < (int)B.size() && A[i] >= B[idx]) idx++;
        if (idx < B.size()) {
            idx++;
            nwin++;
        }
    }
    return nwin;
}