C++로 만들 수 있는 좌표 쌍의 개수 구하기

2차원 평면 위에 2n개의 좌표가 주어져 있다고 가정해 봅시다. 이 좌표들은 두 개의 배열 coordA와 coordB로 나누어 주어지며, 각 좌표는 정수 쌍으로 표현됩니다. 우리의 목표는 coordA에서 한 점과 coordB에서 한 점을 짝지어 좌표 쌍을 만드는 것입니다. 단, 쌍을 이룰 수 있는 조건은 coordA의 점의 x좌표가 coordB의 점의 x좌표보다 작고, 동시에 coordA의 점의 y좌표가 coordB의 점의 y좌표보다 작아야 한다는 것입니다. 또한 한 점이 여러 쌍에 중복해서 속할 수는 없습니다. 이렇게 만들 수 있는 쌍의 개수를 구하는 프로그램을 작성해야 합니다.

예를 들어 입력이 n = 3, coordsA = {{1, 3}, {2, 4}, {4, 3}}, coordsB = {{2, 2}, {4, 2}, {0, 2}}와 같이 주어진다면 출력은 1이 됩니다.

이 경우 만들 수 있는 쌍은 (1, 3)과 (0, 2) 하나뿐입니다.

해결 접근 방법

이 문제는 정렬과 그리디(greedy) 기법을 활용하여 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.

각 점의 사용 여부를 저장하기 위해 크기 100의 배열 chk를 선언하고 모든 요소를 0으로 초기화합니다.
배열 coordA를 오름차순으로 정렬합니다.
배열 coordB를 오름차순으로 정렬합니다.
카운터 변수 k를 0으로 초기화합니다.
i를 n − 1부터 0까지 1씩 감소시키며 반복하고, 각 i마다 j를 0부터 n − 1까지 1씩 증가시키며 검사합니다. 만약 chk[j]가 0이고, coordA[i]의 첫 번째 값이 coordB[j]의 두 번째 값보다 작으며, coordA[i]의 두 번째 값이 coordB[j]의 첫 번째 값보다 작다면 chk[j]를 1로 표시하고 k를 1 증가시킨 뒤 내부 반복문을 종료합니다.
모든 반복이 끝나면 k를 출력합니다. 이 값이 만들 수 있는 좌표 쌍의 개수입니다.

정렬된 coordA를 큰 값부터 차례대로 확인하면서, 아직 사용되지 않은 coordB의 점 중 조건을 만족하는 첫 번째 점과 매칭하는 방식입니다. 각 점은 최대 한 번만 사용되므로 중복 없이 쌍을 만들 수 있으며, 이중 반복문으로 인해 전체 시간 복잡도는 O(n²)입니다.

예제

아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
#define N 100
void solve(int n, vector<pair<int,int>> coordA, vector<pair<int,int>>coordB){
    int i, j, k;
    int chk[100] = {0};
    sort(coordA.begin(),coordA.end());
    sort(coordB.begin(),coordB.end());
    k = 0;
    for(i = n - 1; i >= 0; i--) {
        for(j = 0; j < n; j++) {
            if(chk[j] == 0 && coordA[i].first < coordB[j].second && coordA[i].second < coordB[j].first) {
                chk[j] = 1;
                k++;
                break;
            }
        }
    }
    cout<< k;
}
int main() {
    int n = 3;
    vector<pair<int,int>> coordsA = {{1, 3}, {2, 4}, {4, 3}};
    vector<pair<int,int>> coordsB = {{2, 2}, {4, 2}, {0, 2}};
    solve(n, coordsA, coordsB);
    return 0;
}

입력

3, {{1, 3}, {2, 4}, {4, 3}}, {{2, 2}, {4, 2}, {0, 2}}