프로그래머스 - 숫자 게임

프로그래머스 - 숫자 게임

승점이 최대가 되도록 하려면 A[i]에 가장 작은 차이로 이기는 B[j]를 매핑해줘야한다.
A : [5,1,3,7] / B : [2,2,6,8]
의 경우 A의 5를 B의 6으로, 1을 B의 2로, 3을 B의 8로 매핑해주면 3점이 된다. (7을 8로 매핑해줘도 된다.)
이는 즉, Greedy하게 A[i]보다 큰 B[j]들 중 가장 작은 값을 선택한다는 것이다.
이를 위해 A와 B를 먼저 정렬하고, B의 인덱스를 1씩 증가시키면서 A보다 값이 큰 경우 A의 인덱스를 1 증가시키고, 승점을 1점 올려주면 된다.

코드는 다음과 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    
    sort(B.begin(), B.end());
    sort(A.begin(), A.end());
    
    int n = A.size();
    int a_idx = 0;
    int b_idx = 0;
    while(1) {
        if(a_idx == n || b_idx == n)
            break;
        if(B[b_idx] > A[a_idx]) {
            a_idx++;
            answer++;
        }   
        b_idx++;
    }
    
    return answer;
}