입력

인자 1 : papers

• 배열을 요소로 갖는 배열
• papers.length는 30 이하
• papers[i]는 number 타입을 요소로 갖는 배열
• papers[i]는 차례대로 직사각형의 좌측 하단 모서리의 x좌표, y좌표, 너비(width), 높이(height)
• papers[i][j]는 10,000 이하의 양의 정수

출력

• number 타입을 리턴해야 합니다.

입출력 예시

let result = shadowOfPapers([[0, 1, 4, 4]]);
console.log(result); // --> 16

/*
4 | x x x x
3 | x x x x 
2 | x x x x 
1 | x x x x 
0 |   
--------------
    0 1 2 3 4 
*/

result = shadowOfPapers([
  [0, 0, 4, 4],
  [2, 1, 2, 6],
  [1, 5, 5, 3],
  [2, 2, 3, 3],
]);
console.log(result); // --> 36
/*
7 |   x x x x x
6 |   x x x x x
5 |   x x x x x
4 |     x x x
3 | x x x x x
2 | x x x x x
1 | x x x x
0 | x x x x
------------------
    0 1 2 3 4 5 6 7
*/

[나의 풀이]

function shadowOfPapers(papers) {

  // 1. papers[i]의 원소를 재구성하여
  //    시작점과 (끝점+1)을 쌍으로 나타내는 새로운 배열(verticals)를 만든다.
  //    1-1. 사각형 시작점 [x좌표, y하단 좌표, y상단 좌표, 시작 flag]
  //    1-2. 사각형 끝점+1 [x좌표 + width, y하단 좌표, y상단 좌표, 종료 flag]
  // 2. verticals를 시작과 끝점 상관없이 x 좌표 기준으로 오름차순 정렬한다.
  // 3. 높이를 의미하는 10000 + 1 크기의 배열을 선언하고 0으로 채운다.(height)
  // 4. verticals 의 원소를 순서대로 탐색한다.
  //    4-1. verticals[i][3]이 시작 flag이면 height의 y상단~y하단 index에 1을 더한다.
  //    4-2. verticals[i][3]이 종료 flag이면,
  //         verticals[i - 1][0]과 verticals[i][0]의 차가 너비,
  //         height의 0이 아닌 원소의 갯수가 높이이므로 넓이를 구하고,
  //         height의 y하단~y상단 index에 1을 감소시킨다.
  // 5. 4에서 구한 사각형의 넓이를 모두 더하여 리턴한다.

  const merge = (arr1, arr2) => {
    const mArr = [];
    let i = 0;
    let j = 0;
    while( i < arr1.length && j < arr2.length ){
      if(arr1[i][0] <= arr2[j][0]){
        mArr.push(arr1[i]);
        i++;
      } else {
        mArr.push(arr2[j]);
        j++;
      }
    }
    for( i ; i < arr1.length ; i++ ){
      mArr.push(arr1[i]);
    }
    for( j ; j < arr2.length ; j++ ){
      mArr.push(arr2[j]);
    }
    return mArr;
  }
  const mergeSort = (arr) => {
    if(arr.length <= 1) return arr;
    const half = Math.ceil(arr.length / 2);
    const left = mergeSort(arr.slice(0, half));
    const right = mergeSort(arr.slice(half));
    const result = merge(left, right);
    return result;
  }

  const verticals = [];
  for ( let i = 0 ; i < papers.length ; i++ ){
    verticals.push([papers[i][0], papers[i][1], papers[i][1] + papers[i][3] - 1, true]);
    verticals.push([papers[i][0] + papers[i][2], papers[i][1], papers[i][1] + papers[i][3] - 1, false])
  }

  const sorted = mergeSort(verticals);
  const height = new Array(10001).fill(0);
  for( let i = sorted[0][1] ; i <= sorted[0][2] ; i++ ){
    height[i]++;
  }
  let sum = 0;
  for( let i = 1 ; i < sorted.length ; i++ ){
    if(sorted[i][3]){
      let width = sorted[i][0] - sorted[i - 1][0];
      let length = height.reduce((acc, cur) => cur === 0 ? acc : acc + 1, 0);
      sum += width * length;
      for( let j = sorted[i][1] ; j <= sorted[i][2] ; j++ ){
        height[j]++;
      }
    } else {
      let width = sorted[i][0] - sorted[i - 1][0];
      let length = height.reduce((acc, cur) => cur === 0 ? acc : acc + 1, 0);
      sum += width * length;
      for( let j = sorted[i][1] ; j <= sorted[i][2] ; j++ ){
        height[j]--;
      }
    }
  }
  return sum;
}