카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java)

카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java)

이 문제는 n이 5000이므로 O(N^2)으로 풀어야 합니다.

N^3으로 풀 수 있습니다만,, 최적화 과정이 들어가야 통과됩니다.

문제 출제 목적에 맞게 O(N^2)으로 푸셔야 맞습니다.

(문제는 프로그래머스에서 다시 풀 수 있습니다.)

---

O(N^2)의 해법은 다음과 같습니다. 

1. 세그먼트 트리 개념과 비슷하게 주어진 범위의 직사각형 내부에 쐐기가 몇개 있는지를 먼저 구해놓습니다. -> O(N^2) 
S[i][j] : (0, 0) ~ (i, j) 범위의 직사각형 내부에 존재하는 쐐기의 개수

2) 그리고 모든 쐐기의 쌍에 대하여 -> O(N^2) 

미리 구해놓은 S 배열의 값을 검사하여

값이 0인 경우 (내부에 쐐기가 없음) 텐트를 설치할 수 있음을 쉽게 판단할 수 있습니다. 

예를 들어, (2, 2) ~ (3, 3) 범위의 직사각형 내부에 쐐기가 존재하는지 검사하려면? 
S[3][3] - S[2][3] - S[3][2] + S[2][2] 

예를 들어, (2, 2) ~ (4, 4) 범위의 직사각형 내부에 쐐기가 존재하는지 검사하려면? 

S[3][3] - S[1][3] - S[3][1] + S[1][1]

 

, 

그런데 문제는 x값과 y값의 범위가 2^31-1 이라는 것입니다. 
(2^31 2^31 크기의 int 배열 -선언 불가) 

여기서 좌표 압축이라는 개념이 들어갑니다. 

예를 들어 주어진 x 좌표가 [0, 100, 10000, 2345520]인 경우 
좌표 압축을 통해 [0, 1, 2, 3] 으로 표현할 수 있습니다. 

예를 들어 주어진 (x, y)좌표가 [0, 0], [100, 100], [0, 200], [200, 0] 인 경우에는? 
[0, 0], [1, 1], [0, 2], [2, 0] 이렇게 압축할 수 있습니다. 

따라서 우리는 좌표 압축 기법을 사용하여 
S 배열의 사이즈를 (2^31-1 2^31-1) 가 아닌 (N * N)으로 설정할 수 있습니다.

,

즉, 쉽게 말하면 [0, 0], [100000000, 100000000] 인 경우나

[0, 0], [1, 1]인 경우나 똑같다는 것이죠.

,

일단 위 개념만 알면 쉽게 푸실 수 있을 것입니다.

코드 보시고 이해하기 어려우신 부분은

댓글 남겨주시면 코드 단위로 설명 드리겠습니다.

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

    // 좌표 압축
    ArrayList<Integer> xList = new ArrayList<>();
    ArrayList<Integer> yList = new ArrayList<>();

    for (int i = 0; i < n; i++) {

        xList.add(data[i][0]);
        yList.add(data[i][1]);
    }

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

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

    // 구간합 배열
    int[][] S = new int[n][n];

    for (int i = 0; i < n; i++) {

        int x = uniqueXList.indexOf(new Integer(data[i][0]));
        int y = uniqueYList.indexOf(new Integer(data[i][1]));

        // 좌표 압축 적용
        data[i][0] = x;
        data[i][1] = y;

        // 구간합 배열 초기값
        S[x][y] = 1;
    }

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

            S[i][j] += (i - 1 >= 0 ? S[i - 1][j] : 0)
                    + (j - 1 >= 0 ? S[i][j - 1] : 0)
                    - (i - 1 >= 0 && j - 1 >= 0 ? S[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]);

            startX++;
            startY++;
            endX--;
            endY--;

            int cnt;

            if (startX > endX || startY > endY) {

                cnt = 0;
            }
            else {

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

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

    return ans;
}

17.10.27 수정

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

    // 좌표 압축
    ArrayList<Integer> xList = new ArrayList<>();
    ArrayList<Integer> yList = new ArrayList<>();

    for (int i = 0; i < n; i++) {

        xList.add(data[i][0]);
        yList.add(data[i][1]);
    }

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

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

    // 구간합 배열
    int[][] S = new int[n][n];

    for (int i = 0; i < n; i++) {

        int x = uniqueXList.indexOf(new Integer(data[i][0]));
        int y = uniqueYList.indexOf(new Integer(data[i][1]));

        // 좌표 압축 적용
        data[i][0] = x;
        data[i][1] = y;

        // 구간합 배열 초기값
        S[x][y] = 1;
    }

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

            S[i][j] += (i - 1 >= 0 ? S[i - 1][j] : 0)
                    + (j - 1 >= 0 ? S[i][j - 1] : 0)
                    - (i - 1 >= 0 && j - 1 >= 0 ? S[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 = S[endX - 1][endY - 1] - S[endX - 1][startY] - S[startX][endY - 1] + S[startX][startY];
            }

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

    return ans;
}