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

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제에서 중요한 점은 두 쐐기로 직사각형을 만들었을 때, 그 안에 다른 쐐기가 없어야 한다는 점이다.

단순히 두 쐐기를 정하고 다른 쐐기가 안에 있는지 센다면, 시간복잡도가 O(n^3)으로 매우 커지게 된다.

 

하지만, 정렬을 잘 한다면 O(n^2)으로도 쉽게 풀 수 있는 문제다.

한번 쐐기의 데이터들을 그림으로 생각해 보자

세로 축을 y, 가로 축을 x라고 하면, 쐐기들의 정보를 y축, x축의 순서로 오름차순 정렬을 한다. 

그러면 위 그림과 같이 쐐기들의 순서가 정렬이 될 것이다.

이제 1번 쐐기부터 탐색을 시작한다.

 

1번 쐐기와 연결할 수 있는 쐐기들은 2~7번 쐐기다.

여기서 2, 3번 쐐기는 1번 쐐기와 y축 값이 같으므로 패스한다.

 

4번 쐐기는 높이와 x축이 다르므로, 직사각형을 만들 수 있다.

여기서 중요한 점은 직사각형이 만들어 졌으므로, 4번축의 x값을 저장해 둔다.

x값은 직사각형 안에 쐐기가 있는지 체크하기 위해서 사용하는 값이다. (아래 그림에서 설명)

 

다음으로 5번 쐐기를 비교한다.

5번 쐐기는 이전의 4번 쐐기와 높이가 같으므로, 4번 쐐기의 x값이 5번 쐐기의 x값보다 작아도 직사각형을 만들 수 있다.

이 때, 이전 쐐기와 값을 비교해 4번 쐐기와 5번 쐐기 중 1번 쐐기의 x좌표와 가장 값이 가까운 값을 저장한다.

 

이제 6번 쐐기를 비교할 차례인데, 5번축과 y축의 높이가 다르므로 이전에 저장해 두었던 x값을 가져온다.

6번 쐐기를 비교할 차례에서 만들 수 있는 직사각형의 y 범위는 초록색과 같다.

즉, y 범위안에 있는 쐐기들 중 기준이 되는 1번 쐐기의 x값에 가장 가까운 값을 갱신해 나가는 것이다.

이렇게 사용할 경우 한번의 비교만으로도 두 쐐기 사이에 다른 쐐기가 있는지 판단할 수 있다.

 

6번 쐐기의 x값은 저장된 값인 3보다 작으므로 1번 쐐기와 직사각형을 만들 수 있다.

하지만 7번 쐐기는 x값이 4로 저장된 3보다 크기 때문에, 1번쐐기와 7번 쐐기 사이에 다른 쐐기가 존재한다는 뜻이다. 

 

참고로 항상 기준이 되는 좌표보다 x축의 값이 작은지 큰지 비교해야한다.

아래 그림은 2번 쐐기를 기준으로 탐색을 시작한 경우다.

 2번 쐐기를 기준으로 6번 쐐기는 좌측이고 7번 쐐기는 우측이다.

그러므로 좌측에 있는 쐐기들은 항상 가장 큰 x 값을 저장하고, 우측에 있는 쐐기들은 가장 작은 x값을 저장한다.

 

(즉, 기준이 되는 쐐기와 x값이 다르면서 가장 가까운 x값을 2개 이용한다)

1. 기준 쐐기의 x값보다 작은 값 중 가장 큰 값

2. 기준 쐐기의 x값 보다 큰 값 중 가장 작은 값

  

[아이디어 정리]

1. 좌표를 y축과 x축을 기준으로 오름차순 정렬한다.
2. 첫 좌표를 기준으로 y축의 값이 바뀔 때 마다 가장 기준 쐐기에 가까운 x의 값을 갱신한다.
3. 만약 비교한 쐐기의 x값보다 기준이 되는 쐐기의 x값에 가까운 값이 있다면, 직사각형을 만들 수 없다.
4. 최종적으로 만든 직사각형의 개수를 return한다.

 

 

Code

 

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

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    sort(data.begin(),data.end(),[](vector<int> a, vector<int>b){
        return a[0]==b[0]?a[1]<b[1]:a[0]<b[0];
    });    
    int upV,downV,tempUp,tempDown; //실제로 비교하는 변수, 높이가 변하기 전까지 값을 저장할 변수
    for (int i=0; i<data.size(); i++)
    {
        upV=pow(2,31)-1,downV=0;
        tempUp=upV,tempDown=downV;
        for (int j=i+1; j<data.size(); j++)
        {
            if (data[j-1][0]!=data[j][0])
            { // 높이가 변하는 경우 값을 갱신
                upV=tempUp;
                downV=tempDown;                
            }
            if (data[j][1]==data[i][1]||data[i][0]==data[j][0])
            {
                continue;
            }
            else if (data[j][1]>data[i][1])
            {
                if (upV>=data[j][1])
                {
                    answer+=1;
                }
                tempUp=min(tempUp,data[j][1]);
            }
            else if (data[j][1]<data[i][1])
            {
                if (downV<=data[j][1])
                {
                    answer+=1;
                }
                tempDown=max(tempDown,data[j][1]);
            }
        }        
    }        
    return answer;
}

 

---

문제를 푸는 방법을 그림으로 그려보면 정렬을 이용해 쉽게 풀 수 있는 문제라는 것을 알 수 있다.

처음에 높이가 같은 경우에도 x축의 값이 작아도 제외되는 경우가 생겼는데, 빠르게 찾아 문제를 해결할 수 있었다.

EZ

프로그래머스