[프로그래머스 - 자바] 캠핑

문제 링크

• 캠핑

풀이

• 구간합과 좌표 압축 개념을 몰라서 내 방식대로 접근했지만 틀렸다.
  • x좌표 순으로 정렬한 후 y좌표 상한선과 y좌표 하한선 이내에 좌표가 위치할 경우 answer++를 하고 y좌표 상/하한선을 좁히는 방식
  • 구간합과 좌표 압축은 참고 자료에 잘 설명되어 있다.
• n이 5000이하이기 때문에 O(n^2)까지 허용한다. 이를 통해 구간합 dp 방식을 떠올려야 했다.
• 다만 좌표 범위가 21억까지인 것이 걸린다. 여기서는 좌표의 절대적인 값보다 상대적인 값이 중요하기 때문에 좌표 압축을 떠올려야 했다.

코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] data) {
        int answer = 0;
        int[][] dp = new int[5000][5000];

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

        for (int[] p : data) {
            xList.add(p[0]);
            yList.add(p[1]);
        }

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

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

        for (int i = 0; i < n; i++) {
            data[i][0] = uniqueXList.indexOf(xList.get(i));
            data[i][1] = uniqueYList.indexOf(yList.get(i));

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


        // dp(구간합) 구하기
        for (int r = 0; r < 5000; r++) {
            for (int c = 0; c < 5000; c++) {
                if (r - 1 >= 0) {
                    dp[r][c] += dp[r - 1][c];
                }

                if (c - 1 >= 0) {
                    dp[r][c] += dp[r][c - 1];
                }

                if (r - 1 >= 0 & c - 1 >= 0) {
                    dp[r][c] -= dp[r - 1][c - 1];
                }
            }
        }

        Arrays.sort(data, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int x1 = Math.min(data[i][0], data[j][0]);
                int y1 = Math.min(data[i][1], data[j][1]);
                int x2 = Math.max(data[i][0], data[j][0]);
                int y2 = Math.max(data[i][1], data[j][1]);

                if (x1 == x2 || y1 == y2) {
                    continue;
                }

                int count = dp[y2 - 1][x2 - 1] - dp[y2 - 1][x1] - 
                			  dp[y1][x2 - 1] + dp[y1][x1];
                              
                if (count == 0) {
                    answer++;
                }
            }
        }

        return answer;
    }
}

참고 자료

• 카카오 코드 페스티벌 예선 - 캠핑 문제 해설 (Java)
• [BOJ 백준] 구간 합 구하기 5(11660) Java