[그리디] 숫자 게임 - Summer/Winter Coding(~2018)

해결 방법

A, B 벡터를 각각 오름차순으로 정렬해서 낮은 숫자를 가진 사람들부터 출전시켜가며, A팀에서 숫자가 낮은 사람들은 반드시 매칭이 이루어지도록 하는 식으로 접근하면 쉽게 해결할 수 있다.

 

A의 n번째 팀원을 an이라고 하고, B의 n번째 팀원을 bn이라고 하자.

A팀과 B팀의 각 첫 번째 사람인 a1, b1부터 출전시켜서 a1의 숫자가 더 크다면, b1는 A팀의 모든 뒷 사람들을 이길 수 없는 상태임을 알 수 있다. 왜냐하면 A를 오름차순으로 정렬해놓았기 때문이다. 그래서 B팀의 다음 사람(b2)을 출전시켜서 a1와 비교하면 된다.

만약에 b1의 숫자가 더 크다면 B팀의 승점을 1만큼 카운트하고 A팀과 B팀의 다음 사람을 출전시키면 된다. 그리고 매칭에 시도한 B의 팀원은 더 이상 매칭할 일이 없으니 B팀의 차례를 표시하는 변수를 추가해야 한다.

 

A, B의 범위는 각각 최대 10만이기 때문에, 반복문에서 더 이상의 반복이 필요가 없어졌을 때에는 break을 걸어줘야 시간 초과가 나지 않는다. a1, b1이 출전했을 때 b1의 숫자가 더 크다면, B팀의 팀원들은 방금 출전했던 a1과 더 이상 비교할 필요가 없어지므로 break로 반복문을 빠져나가면 된다.

 

위에 기술한 해결 방법을 입출력 예 #1에 적용해보자.

A팀의 팀원들이 가진 숫자는 각각 5, 1, 3, 7으로, 이를 정렬하면 [1, 3, 5, 7]이다.

B팀의 팀원들이 가진 숫자는 2, 2, 6, 8으로, 이미 정렬되어 있다.

Step1) a1<b1 -> 승점1

Step2) a2>b2

Step3) a2<b3 -> 승점2

Step4) a3<b4 -> 승점3

 

 

소스 코드

#include <vector>
#include <algorithm>
using namespace std;

int answer, point;

int solution(vector<int> A, vector<int> B) {
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    for(int i=0;i<A.size();i++){
        for(int j=point;j<B.size();j++){
            if(A[i]<B[j]) {
                answer++;
                point=j+1;
                break; // 방금 출전했던 A[i]와는 더 이상 비교할 필요가 없어지므로 break로 반복문을 빠져나간다.
            }
        }
    }
    return answer;
}

 

정확성, 효율성 모두 만점