[C++] 2017 카카오코드 예선 캠핑

문제 설명

---

캠핑

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

저와 같은 경우는 Hash Map을 사용하여 압축을 진행하였습니다.

(만약 데이터가 [100,121,999999999999]가 있다면 [0,1,2]로 변환가능)

 

1. map구조에 문제에서 주어진 좌표값들을 저장을 합니다.

2. map을 for문을 사용하여 데이터를 탐색하면 자동적으로 크기가 작은 값부터 탐색이 됩니다.(Hash 함수에 의해 value가 정렬되어 있음)

3. for문을 통해 탐색을 함과 동시에 value를 압축한 값으로 저장을 합니다.

 

void coordCompress(vector<vector<int>> &data){
    
    map<int, int> x_mapper;
    map<int, int> y_mapper;
    
    //1. 데이터를 hashmap에 저장(x와 y는 독립적임)
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        if(x_mapper.count(x) == 0)
            x_mapper.insert({x, true});
        if(y_mapper.count(y) == 0)
            y_mapper.insert({y, true});
    }
    
    //좌표 압축을 진행
    int cnt = 0;
    for(auto &elem : x_mapper){ //2. 자동적으로 value가 작은 값부터 탐색됨
        int num = elem.first;
        x_mapper[num] = cnt++; //3. 좌표압축을 진행
    }
    cnt = 0;
    for(auto &elem : y_mapper){ //2. 자동적으로 value가 작은 값부터 탐색됨
        int num = elem.first;
        y_mapper[num] = cnt++; //3. 좌표압축을 진행
    }
    
    //변환된 좌표를 벡터에 저장하지 않고 map에서 계속해서 읽어오는 것은 속도저하를 유발하므로 
    //벡터로 저장을 해야함(map은 tree구조 이므로 데이터를 탐색하는 속도가 vector보다 느림)
    for(int i=0;i<data.size();i++){
        data[i][0] = x_mapper[data[i][0]];
        data[i][1] = y_mapper[data[i][1]];
    }
    M = x_mapper.size();
    N = y_mapper.size();
}

 

2. 부분합

 부분합을 사용하는 이유는 선택한 두 쐐기 사이에 포함되는 쐐기를 쉽게 식별할 수 있기 때문입니다. 

부분합 arr[x][y] = {0,0} ~ {x,y}사이에 있는 쐐기의 수를 의미합니다.

void make_arr(vector<vector<int>> &data){
    
    //압축된 좌표들의 정보로 arr에 좌표를 표시
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        arr[x][y] = 1;
    }
    
    // arr[x][y] = {0,0} ~ {x,y}까지 존재하는 쐐기의 수 
    //태두리의 부분합을 구함
    for(int x = 1; x < M; x++)
        arr[x][0] += arr[x - 1][0];
    for(int y = 1; y < N; y++)
        arr[0][y] += arr[0][y - 1];
    
    //내부의 부분합을 구함
    for(int x = 1; x < M; x++){
        for(int y = 1; y < N; y++){
            arr[x][y] += arr[x - 1][y] + arr[x][y - 1] - arr[x - 1][y - 1];
        }    
    }
}

 

위의 과정 까지 진행했다면 2개의 쐐기를 선택하는 모든 경우에 대해 3가지 조건을 검사합니다.

1. 두 쐐기의 x좌표가 같은지

2. 두 쐐기의 y좌표가 같은지

3. 두 쐐기 사이에 다른 쐐기가 있는지(태두리에 쐐기가 있는 것은 무관함)

int solve(vector<vector<int>> &data){
    
    int cnt = 0;
    
    for(int i = 0; i < data.size(); i++){
        for(int j = i + 1; j < data.size(); j++){
            
            int h_x = max(data[i][0], data[j][0]);
            int h_y = max(data[i][1], data[j][1]);
            int l_x = min(data[i][0], data[j][0]);
            int l_y = min(data[i][1], data[j][1]);
            
            //x가 같거나, y가 같거나, 사이에 쐐기가 있는 경우
            if(h_x == l_x || h_y == l_y || 0 < arr[h_x - 1][h_y - 1] - arr[h_x - 1][l_y] - arr[l_x][h_y - 1] + arr[l_x][l_y])
                continue;  
            cnt++;
        }    
    }
    return cnt;
}

 

 

 

소스 코드

---

#include <vector>
#include <string.h>
#include <iostream>
#include <map>

using namespace std;

int arr[5001][5001];
int M, N;

void coordCompress(vector<vector<int>> &data){
    
    map<int, int> x_mapper;
    map<int, int> y_mapper;
    
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        if(x_mapper.count(x) == 0)
            x_mapper.insert({x, true});
        if(y_mapper.count(y) == 0)
            y_mapper.insert({y, true});
    }
    
    int cnt = 0;
    for(auto &elem : x_mapper){
        int num = elem.first;
        x_mapper[num] = cnt++;
    }
    cnt = 0;
    for(auto &elem : y_mapper){
        int num = elem.first;
        y_mapper[num] = cnt++;
    }
    
    for(int i=0;i<data.size();i++){
        data[i][0] = x_mapper[data[i][0]];
        data[i][1] = y_mapper[data[i][1]];
    }
    M = x_mapper.size();
    N = y_mapper.size();
}

void make_arr(vector<vector<int>> &data){
    
    for(int i=0;i<data.size();i++){
        int x = data[i][0];
        int y = data[i][1];
        arr[x][y] = 1;
    }
    
    for(int x = 1; x < M; x++)
        arr[x][0] += arr[x - 1][0];
    for(int y = 1; y < N; y++)
        arr[0][y] += arr[0][y - 1];
    
    for(int x = 1; x < M; x++){
        for(int y = 1; y < N; y++){
            arr[x][y] += arr[x - 1][y] + arr[x][y - 1] - arr[x - 1][y - 1];
        }    
    }
}

int solve(vector<vector<int>> &data){
    
    int cnt = 0;
    
    for(int i = 0; i < data.size(); i++){
        for(int j = i + 1; j < data.size(); j++){
            
            int h_x = max(data[i][0], data[j][0]);
            int h_y = max(data[i][1], data[j][1]);
            int l_x = min(data[i][0], data[j][0]);
            int l_y = min(data[i][1], data[j][1]);
            
            //x가 같거나, y가 같거나, 사이에 쐐기가 있는 경우
            if(h_x == l_x || h_y == l_y || 0 < arr[h_x - 1][h_y - 1] - arr[h_x - 1][l_y] - arr[l_x][h_y - 1] + arr[l_x][l_y])
                continue;  
            cnt++;
        }    
    }
    return cnt;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<vector<int>> data) {
    
    int answer = 0;
    memset(arr, 0, sizeof(arr));
    M = 0; N = 0;
    
    coordCompress(data);
    make_arr(data);
    
    answer = solve(data);
    return answer;
}