[Programmers][Kakao] 캠핑

난이도 : Level 4

문제링크 

• 캠핑장에 여러개의 쐐기를 박아두었다
• 설치한 쐐기의 좌표값을 가진 2차원 정수형 배열이 주어진다
• 쐐기들 중 한 쌍을 골라 텐트를 칠 수 있다
  • 텐트는 직사각형이여야 한다
    • 양쪽 쐐기가 대각에 위치하도록 하여 텐트를 친다
  • 텐트가 점유하는 영역 내부에 다른 쐐기를 포함하면 안된다
    • 단, 다른 쐐기가 경계에 위치하는 경우는 허용함
• 주어진 쐐기들을 이용하여 만들 수 있는 텐트의 최대 수를 리턴하라

 

• 쐐기의 개수 : 2 ~ 5000
• 쐐기의 x좌표 : 0 ~ 2^31-1
• 쐐기의 y좌표 : 0 ~ 2^31-1

 

해설

• 서로 가까이 인접해 있는 쐐기부터 
• 텐트를 칠 수 있는지 체크하기
  
  • 양쪽 쐐기가 대각선에 위치하는지 확인
  • 양쪽 쐐기 안에 쐐기가 들어있지 않은지 확인
• 전체 경우를 모두 체크하며, 칠 수 있는 텐트의 수를 리턴하기

 

1. 누적합 알고리즘

텐트를 칠 수 있는지 확인하기 위해서는 양쪽 쐐기 안에 쐐기가 들어있지 않은지 확인해야 합니다.

단순히 쐐기쌍을 뽑고, 체크하는 방식으로 반복하면 O(N^3)으로 비용이 많이 듭니다.

그러므로 누적합에 대한 배열을 생성하고 체크시에 활용하는 누적합 알고리즘을 적용해야 합니다.

 

누적합 배열 생성 및 구성

2차원 정수형 배열인 dp[5000][5000] 배열을 선언하고, dp[y][x] 는 '(0,0)부터 (x,y)까지의 쐐기의 누적합'을 할당합니다.

 

1. dp 배열에 쐐기 좌표에 대해 1씩 셋팅합니다.

for (int i = 0; i < n; i++) {
    dp[data[i][1]][data[i][0]] = 1;
}

 

2. 누적합을 구하기 위해 전체 원소를 순회합니다.

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];
        }
    }
}

2차 중첩 for문으로 각 행의 열들을 순차적으로 순회합니다.

가로, 세로로 인접하다면 누적합을 더해줍니다.

그리고, 중복적으로 더해진 값을 빼줍니다. 방문한 점에서 대각선으로 1씩 작은 점의 누적합을 빼줍니다.

 

양쪽 쐐기 내의 쐐기 수 구하기

(y2, x2) ~ (y1, x1) 양쪽 쐐기 내의 수를 구하기 위해서는 누적합 배열을 사용하여 구합니다.

중복된 부분을 빼주면 구할 수 있습니다.

dp[y2][x2] - dp[y2-1][x1] - dp[y1][x2-1] + dp[y1][x1];

 

문제에서는 경계내에서의 쐐기만 포함여부를 따지므로 

(y2-1, x2-1) ~ (y1, x1) 내의 쐐기 수를 가지고 체크합니다.

 

2. 좌표 압축 알고리즘

 주어진 쐐기의 x, y좌표값이 2^31-1 이하까지이므로 누적합 배열의 가로, 세로가 2^31-1여야 합니다.

메모리 사용률이 매우 높아지고, 누적합 배열을 만들기 위해 순회하는 비용도 가로*세로 이므로 성능이 많이 듭니다.

이러한 범위를 모두 커버하기 위해 배열의 크기를 2^31로 잡더라도

분포가 넓게 퍼져있지 않는 경우, 빈공간은 메모리를 사용할 필요도, 계산할 필요도 없는 것입니다.

 

 문제는 텐트를 지을 수 있는 갯수를 묻는 것이므로

텐트를 지을 수 있는 쐐기쌍인지 체크하기 위한 조건인 양쪽 쐐기 안에 쐐기가 포함되어 있는지만 확인하면 됩니다.

그러므로 쐐기의 좌표가 상대적으로 표현되면 문제 푸는데 지장이 없습니다.

 

x, y좌표값이 전체 좌표에서 몇번째 값인지 얻어, data 배열의 좌표값을 압축합니다.

List<Integer> uniqueXList = new ArrayList<>(new HashSet<>(xList));
List<Integer> uniqueYList = new ArrayList<>(new HashSet<>(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));
}

 

3. 코드

• 아래 코드는 출처와 완전히 같습니다.

public int solution(int n, int[][] data) {
    int answer = 0;
    List<Integer> xList = new ArrayList<>();
    List<Integer> yList = new ArrayList<>();

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

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

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

    int[][] dp = new int[5000][5000];
    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;
    }

    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 (x2 == x1 || y2 == y1) {
                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;
}

 

 

블로그 참고

• doforme - [프로그래머스-자바] 캠핑
• 개발하는 두더지 - 좌표 압축 알고리즘
• 셥코딩 - [BOJ 백준] 구간 합 구하기5(11660) Java