C++로 상하좌우에 점이 하나 이상 있는 점의 개수 구하기

문제 설명

이 문제에서는 2차원 평면 위에 놓여 있는 N개의 점이 주어집니다. 우리의 과제는 각 점의 위, 아래, 왼쪽, 오른쪽 중 한 방향이라도 최소 1개의 점이 존재하는 점의 개수를 찾는 것입니다.

즉, 다음 네 가지 조건 중 하나라도 만족하는 인접 점이 있는 모든 점을 세어야 합니다.

위쪽에 점이 있는 경우 − X 좌표는 같고, Y 좌표가 현재 값보다 1 큰 점이 존재
아래쪽에 점이 있는 경우 − X 좌표는 같고, Y 좌표가 현재 값보다 1 작은 점이 존재
왼쪽에 점이 있는 경우 − Y 좌표는 같고, X 좌표가 현재 값보다 1 작은 점이 존재
오른쪽에 점이 있는 경우 − Y 좌표는 같고, X 좌표가 현재 값보다 1 큰 점이 존재

입력·출력 예시

입력 : arr[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}}
출력 : 1

예시에서 조건을 만족하는 점은 (1, 1) 하나뿐입니다. (1, 1)의 위에는 (1, 2), 아래에는 (1, 0), 왼쪽에는 (0, 1), 오른쪽에는 (2, 1)이 모두 존재하기 때문입니다.

풀이 접근법

모든 점 쌍을 비교하면 비효율적이므로, 전처리를 통해 각 점이 조건을 만족하는지 빠르게 판단할 수 있습니다.

핵심 아이디어는 다음과 같습니다. 평면 위의 각 점을 순회하면서, 같은 X 좌표(세로 줄)와 같은 Y 좌표(가로 줄)에 있는 점들의 좌표 최솟값과 최댓값을 미리 계산해 두는 것입니다.

음수 좌표를 배열 인덱스로 사용할 수 있도록 모든 좌표에 오프셋(OFF = 1000)을 더해 양수 범위로 변환합니다.
minX[], maxX[] : 같은 Y 좌표(가로 줄)를 공유하는 점들 중 X 좌표의 최솟값과 최댓값을 저장합니다.
minY[], maxY[] : 같은 X 좌표(세로 줄)를 공유하는 점들 중 Y 좌표의 최솟값과 최댓값을 저장합니다.
어떤 점의 X 좌표가 같은 가로 줄의 최솟값보다 크고 최댓값보다 작다면, 왼쪽과 오른쪽에 점이 존재한다는 의미입니다.
마찬가지로 Y 좌표가 같은 세로 줄의 최솟값보다 크고 최댓값보다 작다면, 위와 아래에 점이 존재한다는 의미입니다.
두 조건을 모두 만족하면 카운트를 1 증가시키고, 최종 결과를 반환합니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
#define MX 2001
#define OFF 1000
struct point {
    int x, y;
};
int findPointCount(int n, struct point points[]){
    int minX[MX];
    int minY[MX];
    int maxX[MX] = { 0 };
    int maxY[MX] = { 0 };
    int xCoor, yCoor;
    fill(minX, minX + MX, INT_MAX);
    fill(minY, minY + MX, INT_MAX);
    for (int i = 0; i < n; i++) {
        points[i].x += OFF;
        points[i].y += OFF;
        xCoor = points[i].x;
        yCoor = points[i].y;
        minX[yCoor] = min(minX[yCoor], xCoor);
        maxX[yCoor] = max(maxX[yCoor], xCoor);
        minY[xCoor] = min(minY[xCoor], yCoor);
        maxY[xCoor] = max(maxY[xCoor], yCoor);
    }
    int pointCount = 0;
    for (int i = 0; i < n; i++) {
        xCoor = points[i].x;
        yCoor = points[i].y;
        if (xCoor > minX[yCoor] && xCoor < maxX[yCoor])
            if (yCoor > minY[xCoor] && yCoor < maxY[xCoor])
                pointCount++;
    }
    return pointCount;
}
int main(){
    struct point points[] = {{1, 1}, {1, 0}, {0, 1}, {1, 2}, {2, 1}};
    int n = sizeof(points) / sizeof(points[0]);
    cout<<"The number of points that have atleast one point above, below, left, right is "<<findPointCount(n, points);
}

실행 결과

The number of points that have atleast one point above, below, left, right is 1

복잡도 분석

시간 복잡도 : 전처리와 검사 단계가 각각 O(N)이므로 전체 시간 복잡도는 O(N + MX)입니다. 점의 개수에 비례하여 선형적으로 처리됩니다.
공간 복잡도 : 좌표 범위 크기(MX)의 배열 4개를 사용하므로 O(MX)입니다.

이처럼 좌표 압축과 전처리를 활용하면 모든 점 쌍을 비교하는 O(N²) 방식 대신 훨씬 효율적으로 문제를 해결할 수 있습니다.