문제링크

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

알고리즘

구현(좌표압축) + 구간합

좌표 압축을 이용한 코드

이 문제에 대해서 구글링을 통해서 알아보니 좌표 압축을 통해서 풀어야한다는 것을 알게되었다.

좌표 압축할려면 일단 정렬된 상태로 만들고 거기서 불필요한 좌표를 지움으로서 탐색 좌표를 줄여주는 형식이였다.

좌표압축을 하고 그걸 구간합을 이용해서 값을 계산-> 구간합 계산을 통해서 0인경우 그안에 쐐기가 없는 것이므로 ans를 +1 해준다.

블로그 참조:

https://stack07142.tistory.com/entry/%EC%B9%B4%EC%B9%B4%EC%98%A4-%EC%BD%94%EB%93%9C-%ED%8E%98%EC%8A%A4%ED%8B%B0%EB%B2%8C-%EC%98%88%EC%84%A0-%EC%BA%A0%ED%95%91-%EB%AC%B8%EC%A0%9C-%ED%95%B4%EC%84%A4-Java

import java.util.*;

class Solution {


    public int solution(int n, int[][] data) {

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

        int[][] dp = new int[5000][5000];

        //좌표 압축 진행
        for (int idx = 0; idx < data.length; idx++) {
            xList.add(data[idx][0]);
            yList.add(data[idx][1]);
        }

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


        Collections.sort(uniqueXList);
        Collections.sort(uniqueYList);

        //좌표 압축 완료
        for (int idx = 0; idx < n; idx++) {
            data[idx][0] = uniqueXList.indexOf(xList.get(idx));
            data[idx][1] = uniqueYList.indexOf(yList.get(idx));

            dp[data[idx][0]][data[idx][1]] = 1;
        }


        // N^2 구간합 구하기
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

                dp[i][j] += (i - 1 >= 0 ? dp[i - 1][j] : 0)
                        + (j - 1 >= 0 ? dp[i][j - 1] : 0)
                        - (i - 1 >= 0 && j - 1 >= 0 ? dp[i - 1][j - 1] : 0);
            }
        }


        int ans = 0;
        // N^2 모든 쐐기 조합에 대하여 검사
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {

                // 조건#1 검사 : 직사각형이 아닌 경우
                if (data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;

                // 조건#2 검사 : 내부에 쐐기가 존재하는 경우
                int startX, startY, endX, endY;

                startX = Math.min(data[i][0], data[j][0]);
                startY = Math.min(data[i][1], data[j][1]);
                endX = Math.max(data[i][0], data[j][0]);
                endY = Math.max(data[i][1], data[j][1]);

                int cnt;

                if (startX + 1 > endX - 1 || startY + 1 > endY - 1) {

                    cnt = 0;
                } else {

                    cnt = dp[endX - 1][endY - 1] - dp[endX - 1][startY] - dp[startX][endY - 1] + dp[startX][startY];
                }

                if (cnt == 0) ans++;
            }
        }
        return ans;
    }
}

실패한 코드

조합을 사용하는 경우 재귀로 돌아가다보니 시간복잡도가 2^n으로 엄청 크다는 것을 몰랐다는게 좀 충격이였다.

그렇다보니 현재 문제에서 시간초과는 당연하게 발생할 수밖에없었음.

import java.util.*;

class Solution {

    //2쌍 뽑기용
    private Point[] choicePoint;

    private int[][] info;
    boolean visited[];

    int result = 0;

    public int solution(int n, int[][] data) {
        choicePoint = new Point[2];
        visited = new boolean[data.length];
        info = data;

        Arrays.sort(info, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0] == o2[0]){
                    return o1[1] - o2[1];
                }
                return o1[0] - o2[0];
            }
        });
        StartChoice(0, 0);

        return result;
    }

    //일단 2쌍을 다뽑아본다.
    private void StartChoice(int depth, int index) {
        if (depth == choicePoint.length) {
            //직사각형을 만족하면서 내부에 좌표가 존재하는 지 체크
            if (isRact(choicePoint) && checkInnerRact(choicePoint)) {
                result += 1;
            }
            return;
        }

        for (int idx = index; idx < info.length; idx++) {
            if (!visited[idx]) {
                if (depth == 1) {
                    if (choicePoint[0].x == info[idx][0] || choicePoint[0].y == info[idx][1]) {
                        continue;
                    }
                }
                visited[idx] = true;
                choicePoint[depth] = new Point(info[idx][0], info[idx][1]);
                StartChoice(depth + 1, idx + 1);
                visited[idx] = false;

            }
        }
    }

    //내부에 하나라도 존재하면 false
    private boolean checkInnerRact(Point[] choicePoint) {
        //두 좌표 사이에 있는 경우는 내부에 있다고 할수 있다.
        int minX = Math.min(choicePoint[0].x, choicePoint[1].x);
        int maxX = Math.max(choicePoint[0].x, choicePoint[1].x);
        int minY = Math.min(choicePoint[0].y, choicePoint[1].y);
        int maxY = Math.max(choicePoint[0].y, choicePoint[1].y);

        Point minPoint = new Point(minX, minY);
        Point maxPoint = new Point(maxX, maxY);

        //두 좌표 사이에 들어가는 경우 -> 쐐기가 포함된다고 체크할 수있다.
        for (int idx = 0; idx < info.length; idx++) {
            //현재 뽑은 두 좌표와 같은 경우는 pass
            Point curPoint = new Point(info[idx][0], info[idx][1]);
            if ((curPoint.x == choicePoint[0].x && curPoint.y == choicePoint[0].y)
                    || (curPoint.x == choicePoint[1].x && curPoint.y == choicePoint[1].y)) {
                continue;
            }
            //작은 좌표보다 크면서 큰좌표보다 작은 경우
            if ((curPoint.x > minX && curPoint.y >minY) && (curPoint.x < maxX && curPoint.y < maxY)) {
                return false;
            }

        }


        return true;
    }

    //직사각형인지 체크 및 넓이 체크
    private boolean isRact(Point[] choicePoint) {
        Point fisrtpoint = choicePoint[0];
        Point secondpoint = choicePoint[1];
        //가로 * 세로가 0보다 큰지 체크 -> 0인경우는 애초에 직사각형이 아니다.
        long width = Math.abs(fisrtpoint.x - secondpoint.x);
        long height = Math.abs(fisrtpoint.y - secondpoint.y);

        if (width * height <= 0) {
            return false;
        }

        return true;
    }


    private class Point {
        int x;
        int y;

        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}