[프로그래머스/Level 3/C++/2017 카카오코드 예선] 캠핑

https://school.programmers.co.kr/learn/courses/30/lessons/1833

- 출처 : 프로그래머스 코딩 테스트 연습

프로그래머스

[문제 요약]

- 캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 n개의 쐐기가 박혀 있다. 캠핑장 이용 고객은 이 쐐기들 중 한 쌍을 골라 다음과 같은 조건을 만족하도록 텐트를 설치해야 한다.

• 텐트는 직사각형 형태여야 한다.
• 텐트의 네 면이 정확하게 동, 서, 남, 북을 향해야 한다.
• 대각에 위치하는 텐트의 두 꼭짓점이 정확하게 선택한 두 개의 쐐기에 위치해야 한다.
• 텐트가 점유하는 직사각형 영역의 넓이는 0보다는 커야 한다.
• 텐트가 점유하는 직사각형 영역 내부에 다른 쐐기를 포함하면 안 된다. (다른 쐐기가 경계에 위치하는 경우는 허용함)

- 당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.
n개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오.

- 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다.

 

[문제 조건]

입력은 쐐기의 개수를 의미하는 정수 n과, n × 2 크기의 2차원 배열 data로 주어지며, 배열의 각 행은 캠핑장에 설치된 쐐기의 x좌표와 y좌표를 의미한다. 제한 조건은 다음과 같다.

• 2 <= n <= 5,000
• n개의 쐐기는 모두 x좌표 0 이상 2^31-1 이하, y좌표 0 이상 2^31-1 이하에 위치한다.
• 입력되는 n개의 쐐기 중 x좌표와 y좌표가 모두 같은 경우는 없다.

[문제 풀이]

일단 문제에서 원하는 바가 무엇인지 알아보자.

 

위의 그림을 기준으로 설명해보자면, 두 점을 고른 뒤 두 점을 직사각형에서 대각에 위치하는 두 꼭짓점이라 생각했을 때 사각형 내부에 다른 쐐기가 존재하지 않는 경우를 모두 찾는 문제다.

 

여기서 사각형의 테두리에 존재하는 쐐기는 괜찮지만 내부에 쐐기가 존재해서는 안된다.

 

그렇다면 두 점을 골랐을 때 내부에 쐐기가 존재하는지 어떻게 알 수 있을까?

 

예를들어 두 점이 (x1, y1) , (x2 , y2) 라고 했을 때 임의의 한 점(k1, k2)가 있다고 하자.

이때 (k1, k2)는 다음과 같은 조건일때 내부에 존재하게 된다.

• k1의 경우, min(x1,x2) < k1 && k1 < max(x1,x2)
• k2의 경우, min(y1,y2) < k2 && k2 < max(y1,y2);

여기서 중요한 점은 부등호가 포함관계가 아니라는 점이 중요한다. 왜냐하면 문제에서 테두리에는 쐐기가 있어도 상관없다고 했기 때문에

 

따라서 필자는 3중 for문으로 주어지는 좌표들을 하나의 축을 기준으로 오름차순으로 정렬한 다음, 선택한 두 점 사이에 있는 좌표들을 확인하면서 내부에 쐐기가 없을때 answer값을 하나 증가시키면서 답을 구하였다.

 

[소스 코드]

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(vector<int> &a, vector<int> &b)
{
    if(a[0] == b[0])
        return a[1] < b[1];
    else 
        return a[0] < b[0];
}

int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    
    sort(data.begin(), data.end(), cmp);
    
    for(int i=0; i<data.size()-1; i++)
    {
        for(int j=i+1; j<data.size(); j++)
        {
            if(data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;

            bool flag = true;
            for(int k=i+1; k<j; k++)
            {
                if(data[i][0] < data[k][0] && data[k][0] < data[j][0])
                {
                    if(min(data[i][1], data[j][1]) < data[k][1] && data[k][1] < max(data[i][1], data[j][1]))
                    {
                        flag=false; break;
                    }
                }
            }
      
            if(flag) answer++;
        }
    }
    
    return answer;
}

굳