프로그래머스 캠핑 [Lv. 3] (C++)

프로그래머스

캠핑장에는 N개의 쐐기가 박혀있다 이 쐐기를 이용해서 텐트를 설치할 수 있는데, 텐트는 직사각형의 형태여야하며, 텐트의 대각에 위치하는 두 꼭지점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다. 또한 텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안된다. 이때, 텐트를 설치할 수 있는 모든 경우의 수를 구하시오.

 

풀이 방법

모든 쐐기의 위치를 y 오름차순으로 정렬합니다. (y가 같다면 x 오름차순이 되도록)

위와 같은 상황이라면 아래처럼 정렬됩니다.

[0, 0], [0, 2], [1, 1], [2, 0]

 

0번 쐐기부터, 3번 쐐기까지 탐색을 시작합니다.

 

vector<pair<int, int>> points;
for (auto& d : data)
    points.push_back({d[0], d[1]});
sort(points.begin(), points.end(), cmp);

for (int i = 0; i < points.size(); i++)
{
    for (int j = i+1; j < points.size(); j++)
    {
    ... ..
    ... ..

모든 쐐기들 끼리 매칭을 시도하여 직사각형을 만들 수 있는지 체크합니다.

 

int minY = points[i].first;
int maxY = points[j].first;
int minX = min(points[i].second, points[j].second);
int maxX = max(points[i].second, points[j].second);

if (minY == maxY || minX == maxX)
    continue;

직사각형으로 만들 수 없다면 건너뛰게 됩니다.

 

bool flag = true;

for (int k = i + 1; k < j; k++)
{
    int y = points[k].first;
    int x = points[k].second;
    if (y > minY && y < maxY && x > minX && x < maxX)
    {
        flag = false;
        break;
    }
}

if (flag){
    answer++;
}

직사각형으로 만들 수 있다면 i와 j 사이에 있는 쐐기들이 해당 직사각형 안에 위치하는지 찾아줍니다. (정렬을 해준 상태이기 때문에 비교적 빠르게 탐색이 가능합니다)

안에 없다면 answer을 1 늘리고 출력합니다.

 

정답 코드

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    if (a.first == b.first)
        return a.second < b.second;
    
    return a.first < b.first;
}

int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    
    vector<pair<int, int>> points;
    for (auto& d : data)
        points.push_back({d[0], d[1]});
    sort(points.begin(), points.end(), cmp);

    for (int i = 0; i < points.size(); i++)
    {
        for (int j = i+1; j < points.size(); j++)
        {
            int minY = points[i].first;
            int maxY = points[j].first;
            int minX = min(points[i].second, points[j].second);
            int maxX = max(points[i].second, points[j].second);
            
            if (minY == maxY || minX == maxX)
                continue;
            
            bool flag = true;
            
            for (int k = i + 1; k < j; k++)
            {
                int y = points[k].first;
                int x = points[k].second;
                if (y > minY && y < maxY && x > minX && x < maxX)
                {
                    flag = false;
                    break;
                }
            }
          
            if (flag){
                answer++;
            }
            
        }
    }
    
    return answer;
}