<Algorithm> 205. 캠핑(Programmers)

1. 캠핑(Programmers)

   사용 알고리즘 :  좌표압축, 구간합

• 다른 블로그를 보면서 힘겹게 이해한 문제, 일반적인 알고리즘보다 확실히 어렵다는 느낌이 들었다.

• 이문제를 풀면서 좌표압축하는 방법을 확실하게 알 수 있었다.(배열의 인덱스가 아닌 상대적 위치만 필요로 할때 사용)

문제에 대한 접근&생각

1. 좌표의 범위가 2^31-1 이고 대각선으로 떨어져 있으면 텐트를 만들 수 있음 -> 좌표압축!
2. 내부에 쐐기가 있는 경우 제외, 경계에 있는 쐐기는 허용 -> 결과조건!
3. 내부에 쐐기가 있는 경우에 대한 예외처리 -> 구간합!

코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79

import java.util.ArrayList; import java.util.List; import java.util.stream.Collectors;   public class Solution {     public static void main(String[] args) {         System.out.println(new Solution().solution(4, new int[][] {{0,0},{1,1},{0,2},{2,0}}));     }     public int solution(int n, int[][] data) {       int answer = 0;       /******************************        * 좌표 압축과 2차원 배열의 구간합을 이용해서        * 텐트를 칠 수 있는 경우의 수를 모두 구한다.        *******************************/              // 좌표압축       List<Integer> xList = new ArrayList<>();       List<Integer> yList = new ArrayList<>();              for(int i = 0; i < n; i++) {           xList.add(data[i][0]);           yList.add(data[i][1]);       }       xList = xList.stream().distinct().sorted().collect(Collectors.toList());       yList = yList.stream().distinct().sorted().collect(Collectors.toList());       //System.out.println(Arrays.toString(xList.toArray()));       int[][] s = new int[n][n];              for(int i = 0; i < n;i++) {           int x = xList.indexOf(new Integer(data[i][0]));           int y = yList.indexOf(new Integer(data[i][1]));           data[i][0] = x;           data[i][1] = y;           s[x][y] = 1;       }              // 구간합       for(int i = 0; i < n; i++) {           for(int j = 0; j < n; j++) {               if(i != 0) {                   s[i][j] += s[i-1][j];               }               if(j != 0) {                   s[i][j] += s[i][j-1];               }               if(i !=0 && j != 0) {                   s[i][j] -= s[i-1][j-1];               }           }       }              for(int i = 0; i < n; i++) {           for(int j = i+1; j< n; j++ ) {                              // 대각선이 아닐 경우                if(data[i][0] == data[j][0] || data[i][1] == data[j][1]) continue;                              int minx = Math.min(data[i][0], data[j][0]);               int miny = Math.min(data[i][1], data[j][1]);               int maxx = Math.max(data[i][0], data[j][0]);               int maxy = Math.max(data[i][1], data[j][1]);                              int count;               // 내부의 쐐기가 있는지 판단               if(minx + 1 > maxx-1 || miny+ 1 > maxy-1) {                   count = 0;               }else {                   count = s[maxx-1][maxy-1] - s[minx][maxy-1] - s[maxx-1][miny] + s[minx][miny];               }                              // 쐐기가 없을 경우 카운팅               answer = (count==0)? answer+1:answer;           }       }              return answer;     } }   Colored by Color Scripter

cs

출처  

https://stack07142.tistory.com/289