[ 프로그래머스 캠핑 (Lv4) ] (C++)

프로그래머스의 캠핑(Lv4) 문제이다.

[ 문제풀이 ]

먼저, 주어지는 좌표의 크기를 보게 되면 최대 2^31 - 1 이기 때문에, 2차원 배열로 좌표마다 실제로 체크를 해주면서 구현을 진행하는 것은 불가능하다. 입력되는 좌표값의 크기가 너무 크기 때문에 2차원 배열을 선언을 할 수가 없다.

그래서 본인은 단순히 좌표값의 크기들을 비교하는 식으로 진행해주었다.

비교하기 위해서 먼저 좌표들을 오름차순으로 정렬시켜 주었다. 그리고 '텐트를 설치할 수 있는' 좌표들을 2개를 선택해 주는 것이다. 넓이가 0이 되면 안되기 때문에, x좌표가 같은 2개의 좌표를 선택하거나, y좌표가 같은 2개의 좌표를 선택하지 못하도록 구현해 주었다.

쐐기가 직사각형의 내부에 포함되는 조건은 다음과 같이 판단할 수 있다.

텐트를 만들려는 좌표 2개가 (x , y) , (xx , yy) 라고 가정했을 때, 쐐기의 좌표가 (a , b) 라고 가정해보자.

이 때, (a, b)가 (x, y)와 (xx, yy)가 이루는 텐트 안에 있다는 것은, x <= a <= xx 이고, y <= b <= yy 라는 것을 의미한다.

즉 ! 이런 경우에는 (x, y)와 (xx, yy)로 텐트를 만들 수 없다는 것을 의미한다.

실제 구현에서는 3중 for문을 통해서 구현해주었다.

첫 번째 for문은 "텐트를 지을 첫 번째 쐐기의 좌표 선택"

두 번째 for문은 "텐트를 지을 두 번째 쐐기의 좌표 선택"

세 번째 for문은 "첫 번째 for문과 두 번째 for문으로 선택한 좌표들로 텐트를 만들 때, 해당 텐트를 만들 수 있는지 다른 쐐기들과 좌표를 비교하기 위해서 '쐐기들의 좌표를 선택'" 하기 위한 for문이다.

[ 소스코드 ]

#include <vector>
#include <algorithm>
using namespace std;
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
 
int Min(int A, int B) { if (A < B) return A; return B; }
int Max(int A, int B) { if (A > B) return A; return B; }
 
int solution(int n, vector<vector<int>> data) 
{
    int answer = 0;
    sort(data.begin(), data.end());
    for (int i = 0; i < n; i++)
    {
        int x = data[i][0];
        int y = data[i][1];
 
        for (int j = i + 1; j < n; j++)
        {
            int xx = data[j][0];
            int yy = data[j][1];
 
            if (x == xx || y == yy) continue;
            
            bool Flag = true;
            for (int k = i + 1; k < j; k++)
            {
                int cx = data[k][0];
                int cy = data[k][1];
                if ((x < cx && cx < xx) && (Min(y, yy) < cy && cy < Max(y, yy)))
                {
                    Flag = false;
                    break;
                }
            }
            if (Flag == true) answer++;
        }
    }
    return answer;
}