C++로 축의 한쪽 면에 모든 점이 남도록 제거해야 하는 최소 점 개수 구하기

문제 설명

데카르트 좌표 평면에 N개의 점이 주어졌을 때, 남은 모든 점이 임의의 축(X축 또는 Y축)의 한쪽 면에 위치하도록 만들기 위해 제거해야 하는 점의 최소 개수를 구하는 문제입니다.

예를 들어 입력이 {(10, 5), (-2, -5), (13, 8), (-14, 7)}라고 해보겠습니다. 이때 점 (-2, -5) 하나만 제거하면 나머지 세 점이 모두 X축 위쪽에 위치하게 됩니다.

따라서 정답은 1입니다.

접근 방법

핵심 아이디어는 매우 단순합니다. 어떤 축의 한쪽 면에 점들을 남기려면, 반대편에 있는 점들을 모두 제거해야 합니다. 따라서 네 방향(Y축 기준 왼쪽·오른쪽, X축 기준 위·아래)에 속한 점의 개수를 각각 센 뒤, 그중 가장 작은 값을 반환하면 곧 최소 제거 횟수가 됩니다.

1. X축과 Y축을 기준으로 각 방향(왼쪽, 오른쪽, 위, 아래)에 있는 점의 개수를 구한다.
2. 네 값 중 최솟값을 반환한다.

변수별 의미

• a : x값이 음수인 점의 개수 (Y축 왼쪽)
• b : x값이 0 이상인 점의 개수 (Y축 오른쪽)
• c : y값이 양수인 점의 개수 (X축 위쪽)
• d : y값이 0 이하인 점의 개수 (X축 아래쪽)

모든 점을 한 번씩만 확인하면 되므로 시간 복잡도는 O(N), 추가 메모리는 상수 공간만 사용하는 O(1)로 매우 효율적입니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct point{
   int x, y;
};
int minPointsToBeRemoved(point arr[], int n){
   int a = 0, b = 0, c = 0, d = 0;
   for (int i = 0; i < n; i++){
      if (arr[i].x >= 0)
         b++;
      else if (arr[i].x <= 0)
         a++;
      if (arr[i].y <= 0)
         d++;
      else if (arr[i].y >= 0)
         c++;
   }
   return min({a, d, c, b});
}
int main(){
   point arr[] = {{10, 5}, {-2, -5}, {13, 8}, {-14, 7}};
   cout << "Minimum points to be removed = " <<
   minPointsToBeRemoved(arr, SIZE(arr)) << endl;
   return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 출력이 생성됩니다.

Minimum points to be removed = 1

입력된 네 점 중 X축 아래쪽(y < 0)에 있는 점은 (-2, -5) 하나뿐이므로, 이 점 하나만 제거하면 나머지 점들이 모두 한쪽 면에 남게 되어 최솟값 1이 출력되는 것을 확인할 수 있습니다.