[프로그래머스] 캠핑

[문제]

캠핑

무지를 돌보느라 지친 콘은 한적한 시골의 한 캠핑장에 놀러 갔다. 캠핑장은 텐트를 칠 수 있는 넓은 평지를 제공하고 있는데, 이 평지에는 이미 캠핑장에서 설치해 놓은 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좌표가 모두 같은 경우는 없다.

출력 형식

입력에 주어진 각 케이스에 대해 가능한 텐트의 쐐기의 쌍의 개수를 정수 형태로 리턴한다.

예제 입출력

ndataanswer

4

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

3

예제에 대한 설명

예제에는 총 4개의 쐐기가 있으며 이 중 (0,0)-(1,1), (0,2)-(1,1), (1,1)-(2,0)의 세 가지 위치에만 텐트를 설치할 수 있다. (0,0)-(0,2)와 (0,0)-(2,0)의 경우에는 직사각형 영역의 넓이가 0이 되기 때문에 조건을 만족하지 못하며, (0,2)-(2,0)의 경우 (1,1) 위치의 쐐기가 직사각형의 내부에 포함되므로 조건을 만족하지 못한다.

 

 

[풀이]

 

1) https://jaejin0me.github.io/post/algo47/ 참고함

 

2) DP문제인 것 같아서 넘기려고 했으나(DP 잘하고 싶다..) 위 블로그를 참고해보니 좌표 압축 알고리즘이라는 새로운 개념이 보여서 풀게 됐다. 

 

3) 좌표 압축 알고리즘은 https://duzi077.tistory.com/163 참고함 

 

4) 두 가지 풀이가 있으나 처음 생각한 방향과 비슷한 풀이로 먼저 풀고, DP로 풀어보려고 한다...

 

5) 처음 생각한 방향은 좌표들을 정렬한 후에 대각선을 이루는 좌표들의 조합을 구해서 직사각형을 이루는 좌표 안에 존재하는 쐐기를 없애는 방향이었다. 

 

6) 일단 대각선을 이루는 좌표의 기본 정의는 (x, y) (x2, y2)가 있다면 x != x2 && y != y2 이다. 

 

7) 만약 대각선을 이루는 좌표를 발견했다면 x값을 기준으로 정렬을 했기 때문에 이전 값들을 살펴보면서 (x값을 기준으로 정렬을 했기 때문에 그 이후의 좌표들은 직사각형 범위 내에 포함되지 않는다.) 안에 있는 지 확인한다. 

 

8) 여기서 막혔는데 왜 이런 생각을 못할까 싶었다. 

그냥 새로운 좌표의 x값이 최우상단의 값(max(x, x2)) 보다 작거나 최좌하단(min(x, x2))보다 크면 중간에 위치한다는 말이기 때문에 직사각형 안에 존재하는 좌표이고 

y값이 최우상단(max(y, y2)) 보다 작거나 최좌하단(min(y, y2))보다 크면 중간에 위치한다.-> answer-- 을 해준다. 

 

그리고 저 조건에 걸리는 값들을 발견하면 이미 대각에 위치한 두 좌표는 쓸모가 없기 때문에 반복문을 종료한다. 

 

9) 이제 좌표 압축하는 방법으로 풀어봐야겠다...

---

#include <vector>
#include <cmath>
#include <iostream>
#include <algorithm>
 
using namespace std;
 
typedef pair<int, int> pp;
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    
    vector<pp> candi;
    
    sort(data.begin(), data.end());
    
    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]) {
                for (int k = j; k >= i; k--) {
                    if (data[k][0] < max(data[i][0], data[j][0]) &&
                       data[k][0] > min(data[i][0], data[j][0]) && 
                        data[k][1] < max(data[i][1], data[j][1]) &&
                        data[k][1] > min(data[i][1] , data[j][1]) ){
                        answer--;
                            break;
                        }  
                }
                  answer++;
            }
        }
    }
    return answer;
}

 

[좌표 압축 알고리즘 사용]

 

#include <vector>
#include <cstring>
#include <unordered_set>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
int dp[5000][5000];
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int> > data) {
    int answer = 0;
    memset(dp, 0, sizeof(dp));
    
    vector<int> xp, yp;
    
    for (int i =0; i < data.size(); i++) {
        xp.push_back(data[i][0]);
        yp.push_back(data[i][1]);
        
    }
    
    unordered_set<int> uniqXp(xp.begin(), xp.end()); //중복 제거
    unordered_set<int> uniqYp(yp.begin(), yp.end()); //중복 제거
    
    xp.clear(); yp.clear(); //중복 제거된 값을 넣기 위해 clear
    
    xp.assign(uniqXp.begin(), uniqXp.end());
    yp.assign(uniqYp.begin(), uniqYp.end());
    
    sort(xp.begin(), xp.end());
    sort(yp.begin(), yp.end());
    
    //좌표 압축 
    int x = 0, y = 0;
    for (int i = 0; i < data.size(); i++) {
        for (int j = 0; j < xp.size(); j++) {
            if (data[i][0] == xp[j]) {
                x = j;
                data[i][0] = x; //좌표를 인덱스로 대체한다.
                break;
            }
        }
        for (int j = 0; j < yp.size(); j++) {
            if (data[i][1] == yp[j]) {
                y = j;
                data[i][1] = y; //좌표를 인덱스로 대체한다.
                break;
            }
            
        }
        dp[x][y] = 1;// 쐐기가 있는 곳 
        
    }
    
    //각 영역별 쐐기의 개수를 누적합
    for (int i = 0; i < data.size(); i++) {
         cout << data[i][0] << " " << data[i][1] << '\n';
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
           
            dp[i][j] +=(i-1 > -1 ? dp[i-1][j]  : 0 ) + (j-1 > -1 ? dp[i][j-1] : 0 ) -(i-1 > -1&& j-1 > -1 ? dp[i-1][j-1] : 0 );
        }
    }
    
    int cnt = 0;
    int sx, sy, ex, ey;
    
    for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
            if (data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;
            
            cnt = 0;
            sx = data[i][0] < data[j][0] ? data[i][0] : data[j][0];
            ex =data[i][0] > data[j][0] ? data[i][0] : data[j][0];
            sy = data[i][1] < data[j][1] ? data[i][1] : data[j][1];
            ey = data[i][1] > data[j][1] ? data[i][1] : data[j][1];
            
            //내부의 공간이 1인 경우 쐐기가 있을 공간이 없다.
            if (sx + 1 > ex-1 || sy + 1 > ey -1) cnt = 0;
            else {
                cnt = dp[ex-1][ey-1] - dp[ex-1][sy] - dp[sx][ey-1] + dp[sx][sy];
            }
            if (cnt == 0) answer++;
        }
    }
    return answer;
}
int main() {
 
    int xy1[] = {0, 0};
    int xy2[] = {1, 2};
    int xy3[] = {0, 2};
    int xy4[] = {2, 0};
    int xy5[] = {0, 3};
    int xy6[] = {3, 2};
    int xy7[] = {1, 4};
    int xy8[] = {4, 4};
    int xy9[] = {100, 50};
    int xy10[] = {150, 30};
 
    vector<int> ixy1(xy1, xy1 + (sizeof(xy1) / sizeof(xy1[0])));
    vector<int> ixy2(xy2, xy2 + (sizeof(xy2) / sizeof(xy2[0])));
    vector<int> ixy3(xy3, xy3 + (sizeof(xy3) / sizeof(xy3[0])));
    vector<int> ixy4(xy4, xy4 + (sizeof(xy4) / sizeof(xy4[0])));
    vector<int> ixy5(xy5, xy5 + (sizeof(xy5) / sizeof(xy5[0])));
    vector<int> ixy6(xy6, xy6 + (sizeof(xy6) / sizeof(xy6[0])));
    vector<int> ixy7(xy7, xy7 + (sizeof(xy7) / sizeof(xy7[0])));
    vector<int> ixy8(xy8, xy8 + (sizeof(xy8) / sizeof(xy8[0])));
    vector<int> ixy9(xy9, xy9 + (sizeof(xy9) / sizeof(xy9[0])));
    vector<int> ixy10(xy10, xy10 + (sizeof(xy10) / sizeof(xy10[0])));
    
    vector<vector<int> > input;
    input.push_back(ixy1);
    input.push_back(ixy2);
    input.push_back(ixy3);
    input.push_back(ixy4);
    input.push_back(ixy5);
    input.push_back(ixy6);
    input.push_back(ixy7);
    input.push_back(ixy8);
    input.push_back(ixy9);
    input.push_back(ixy10);
    
    cout << solution(4000, input) << '\n';
    
}