[Programmers] 캠핑 (Java)

1.  문제 링크

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

2.  문제

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

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

캠핑장에서는 위와 같은 조건을 만족하는 위치라면 어디든 고객이 텐트를 설치할 수 있도록 정확한 크기의 텐트를 모두 구비하여 대여해준다고 한다.
당신은 위와 같은 조건을 만족하는 텐트를 설치할 수 있는 쐐기의 쌍의 개수는 총 몇 가지가 될지 궁금해졌다.
n개의 쐐기의 위치가 좌표로 주어질 때, 위의 조건을 만족하는 쐐기의 쌍의 개수를 계산하는 프로그램을 작성하시오. 단, 동서 방향은 x축, 남북 방향은 y축과 평행하다고 가정한다.

3.  제한사항

입력 형식

입력은 쐐기의 개수를 의미하는 정수 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좌표가 모두 같은 경우는 없다.

출력 형식

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

입출력 예

4.  소스코드

import java.util.*;

class Solution {
	public int solution(int n, int[][] data) {
        // 문제의 범위인 (0 ~ 2^31 - 1)에 해당하는 좌표를 이용하기에는 범위가 너무 크다!
        //  -> 그러므로 좌표 압축을 통해 좌표 범위를 줄여서 이용하겠다!
        //      - ex. 0, 1, 100, 10000, 100000 이러한 좌표들을 0, 1, 2, 3, 4 이렇게 압축하겠다!
        //      - 크기가 작은 좌표들부터 정렬하여 각 좌표를 0, 1, 2, 3.. 이렇게 변경할 것이다

        // 좌표 압축을 위해 중복 없는 x, y 좌표를 얻고 이를 크기에 맞게 정렬한다
        List<Integer> xList = new ArrayList<Integer>();
        List<Integer> yList = new ArrayList<Integer>();
        for(int[] point : data) {
            xList.add(point[0]);
            yList.add(point[1]);
        }

        xList = new ArrayList<Integer>(new HashSet<>(xList));
        yList = new ArrayList<Integer>(new HashSet<>(yList));

        Collections.sort(xList);
        Collections.sort(yList);

        // insideWedgeNum[x][y] = (0, 0) ~ (x, y) 직사각형 내부에 존재하는 쐐기 개수
        // 우선 data에 있는 모든 좌표들을 좌표 압축한 좌표들로 변경하고 insideWedgeNum의 초기값을 설정한다
        int[][] insideWedgeNum = new int[n][n];
        for(int[] point : data) {
            point[0] = xList.indexOf(point[0]);
            point[1] = yList.indexOf(point[1]);

            // 초기화
            insideWedgeNum[point[0]][point[1]] = 1;
        }

        // insideWedgeNum의 각 위치에 알맞은 값을 구한다
        //  - insideWedgeNum[x][y] += (insideWedgeNum[x - 1][y] + insideWedgeNum[x][y - 1] - insideWedgeNum[x - 1][y - 1])
        for(int xIdx = 0; xIdx < n; xIdx++) {
            for(int yIdx = 0; yIdx < n; yIdx++) {
                insideWedgeNum[xIdx][yIdx] += (
                        (xIdx - 1 >= 0 ? insideWedgeNum[xIdx-1][yIdx] : 0)
                                + (yIdx - 1 >= 0 ? insideWedgeNum[xIdx][yIdx - 1] : 0)
                                - (xIdx - 1 >= 0 && yIdx - 1 >= 0 ? insideWedgeNum[xIdx - 1][yIdx - 1] : 0)
                );
            }
        }

        int answer = 0; // 가능한 쐐기의 쌍의 개수
        // 모든 쐐기쌍들을 순회하면서 가능한 쐐기의 쌍을 찾는다
        for(int pointIdx1 = 0; pointIdx1 < n; pointIdx1++) {
            for(int pointIdx2 = pointIdx1 + 1; pointIdx2 < n; pointIdx2++) {
                // x좌표나 y좌표가 같다면 직사각형을 만들 수 없으니 이러한 경우는 제외하고 다른 경우를 살펴본다
                if(data[pointIdx1][0] == data[pointIdx2][0] || data[pointIdx1][1] == data[pointIdx2][1]) continue;

                // 직사각형의 시작 좌표와 끝 좌표를 구한다
                int startX = Math.min(data[pointIdx1][0], data[pointIdx2][0]);
                int startY = Math.min(data[pointIdx1][1], data[pointIdx2][1]);
                int endX = Math.max(data[pointIdx1][0], data[pointIdx2][0]);
                int endY = Math.max(data[pointIdx1][1], data[pointIdx2][1]);

                int wadgeNum = 0; // 현재 직사각형 내부에 존재하는 쐐기의 수
                // 직사각형의 한 변의 길이가 1이라면, 내부에 쐐기가 들어갈 공간이 없으니 이러한 경우는 제외하고 다른 경우에 대해 내부에 존재하는 쐐기의 수를 구한다
                if(startX + 1 <= endX - 1 && startY + 1 <= endY - 1) {
                    wadgeNum = insideWedgeNum[endX - 1][endY - 1] - insideWedgeNum[endX - 1][startY] - insideWedgeNum[startX][endY - 1] + insideWedgeNum[startX][startY];
                }

                // 내부에 존재하는 쐐기의 수가 0이라면 가능한 쐐기의 쌍이므로 정답 개수에 1을 추가한다
                if(wadgeNum == 0) answer++;
            }
        }

        return answer;
    }
}