문제

풀이

좌표(말뚝)의 최대 개수가 5000이므로 이중 반복문을 통해 개수를 세어도 시간초과가 나지 않을 것이라 생각했다.

텐트 설치를 위해서는 다음 조건을 지켜야 한다.
조건 1. x좌표가 같거나 y좌표가 같으면 설치 X
조건 2. x좌표와 y좌표로 만든 직사각형 내부에 다른 말뚝 X

이 조건들을 지키기 위해 먼저 좌표를 정렬해 주었다.
그 후 이중 반복문을 통해 두 좌표를 선택해주었다.
바깥 반복문에서 잡고 있는 기준 좌표를 a좌표,
안쪽 반복문에서 돌아가는 좌표를 b좌표 라고 하자.

순서대로 탐색하는 과정에서
1. a좌표 기준으로 왼쪽에 있는 b좌표 중 가장 오른쪽에 있는 좌표 (maxLoc)
2. a좌표 기준으로 오른쪽에 있는 b좌표 중 가장 왼쪽에 있는 좌표 (minLoc)
를 기록해주며 탐색했다.

그리고 이 minLoc보다 왼쪽에 있거나 동일 선상에 있는 b좌표, maxLoc보다 오른쪽에 있거나 동일 선상에 있는 b좌표만 텐트 설치가 가능한 경우이므로 count+1 을 시켜주면 된다.

그렇지 않은 b좌표는 그 사이에 minLoc이나 maxLoc 좌표가 존재한다는 뜻이므로 텐트 설치가 불가하다.

코드

#include <vector>
#include <algorithm>
#include <cmath>
#include <iostream>
using namespace std;
#define INF 2147483647
int solution(int n, vector<vector<int>> data) {
    int answer = 0;

    sort(data.begin(), data.end());
    for (int i = 0; i < data.size(); i++) {
        pair<int, int> minLoc = { INF,INF }, maxLoc = { -1,-1 };
        pair<int, int> minLocT = { INF,INF }, maxLocT = { -1,-1 };
        int x = data[i][0];
        int y = data[i][1];
        for (int j = i + 1; j < data.size(); j++) {
            int nx = data[j][0];
            int ny = data[j][1];

            if (data[j - 1][0] != data[j][0]) {
                minLocT = minLoc;
                maxLocT = maxLoc;
            }

            if (x == nx || y == ny) continue;
            if (ny < y) {
                if (ny > maxLoc.second) {
                    maxLoc.second = ny;
                    maxLoc.first = nx;
                }
                if (ny >= maxLocT.second || nx == maxLocT.first) answer++;
            }
            else if (ny > y) {
                if (ny < minLoc.second) {
                    minLoc.second = ny;
                    minLoc.first = nx;
                }
                if (ny <= minLocT.second || nx == minLocT.first) answer++;
            }
        }
    }
    return answer;
}