JavaScript Algorithm - shadowOfPapers

 

문제설명: 

좌표평면 위에 존재하는 수많은 직사각형에 대한 정보가 2차원 배열로 주어집니다. 이 직사각형들은 서로 겹쳐 있을(overlapping) 수 있습니다. 이 직사각형들이 이루는 면적을 리턴해야 합니다.

문제를 다르게 표현하면 아래와 같습니다.

- 밑이 투명한 좌표평면 위에 직사각형 모양의 종이를 여러 개 올려놓고 위에서 빛을 비출 때 생기는 그림자의 넓이를 구해야 합니다.

좀 더 쉬운 이해를 위해서는 입출력 예시를 보시는 것을 추천드립니다.

각 배열은 [x, y, width, height]의 요소로 이루어져있습니다.

예를 들어 [0, 1, 4, 4]는 0,1 좌표에서 너비 4, 높이 4로 이루어진 사각형이라고 생각하시면 됩니다. 

 

 

 

입력

인자 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
*/

 

입출력 예시에서 계산되는 과정

/*
모든 좌표가 아닌 높이가 변하는 부분만 계산한다.
색종이에 대한 정보가 아래와 같이 주어졌을 때, 전체 면적을 구하는 알고리즘
const papers = [
  [0, 0, 4, 4],
  [2, 1, 2, 6],
  [1, 5, 5, 3],
  [2, 2, 3, 3],
];

각 사각형의 시작과 끝을 범위(range) 표기로 각각 s(start), e(end)로 표시한다.
e는 사각형이 끝나느 x좌표의 다음 좌표에 표기한다.
7 |   x x x x x
6 |   x x x x x
5 |   s x x x x e
4 |     x x x
3 | x x x x x
2 | x x s x x e
1 | x x s x e
0 | s x x x e
------------------
    0 1 2 3 4 5 6 7

새로운 변화(시작 또는 끝)가 있을 때마다 면적을 계산하여 더한다.

1) 4를 더한다. (면적은 4)
7 |   
6 |   
5 |   
4 |   
3 | x 
2 | x 
1 | x 
0 | s 
------------------
    0 1 2 3 4 5 6 7

2) 7을 더한다. (면적은 11)
7 |   x 
6 |   x 
5 |   s 
4 |     
3 |   x 
2 |   x 
1 |   x 
0 |   x 
------------------
    0 1 2 3 4 5 6 7

3) 16을 더한다. (면적은 27)
7 |     x x 
6 |     x x 
5 |     x x 
4 |     x x 
3 |     x x 
2 |     s x 
1 |     s x 
0 |     x x 
------------------
    0 1 2 3 4 5 6 7

4) 6을 더한다. (면적은 33)
7 |         x 
6 |         x 
5 |         x 
4 |         x
3 |         x
2 |         x 
1 |         
0 |         
------------------
    0 1 2 3 4 5 6 7

4) 3을 더한다. (면적은 36)
7 |            x
6 |            x
5 |            x 
4 |         
3 |         
2 |         
1 |         
0 |         
------------------
    0 1 2 3 4 5 6 7

 

 

 

풀이코드 1 :

const merge = function (left, right, comparator = (item) => item) {
    let merged = [];
    let leftIdx = 0,
      rightIdx = 0;
    //size에 left, right길이 더하기 
    const size = left.length + right.length;
  

    for (let i = 0; i < size; i++) {
      if (leftIdx >= left.length) {
        merged.push(right[rightIdx]);
        rightIdx++;
      } else if (rightIdx >= right.length || comparator(left[leftIdx]) <= comparator(right[rightIdx])) {  
        merged.push(left[leftIdx]);
        leftIdx++;
      } else {
        merged.push(right[rightIdx]);
        rightIdx++;
      }
    }
  
    return merged;
  };
  
  const mergeSort = function (arr, comparator) {
    const aux = (start, end) => {
      if (start >= end) return [arr[start]];
      const mid = Math.floor((start + end) / 2);
      const right = aux(start, mid);
      const left = aux(mid + 1, end);
      return merge(left, right, comparator);
    };
    return aux(0, arr.length - 1);
  };
  
  function shadowOfPapers(papers) {
    // 주어진 사각형의 정보를 각 좌표의 시작과 끝을 나타내는 좌표로 변경하여 저장한다.
    const coordinates = [];
    papers.forEach((p) => {
      const [x, y, width, height] = p;
      // 사각형의 시작점의 x좌표, 하단 y좌표, 상단 y좌표, 사각형의 시작을 알리는 flag
      coordinates.push([x, y, y + height - 1, 1]);
      // 사각형의 마지막점의 x좌표, 하단 y좌표, 상단 y좌표, 사각형의 마지막을 알리는 flag
      // x좌표는 너비 계산에 누락을 방지하기 위해 범위로 저장한다.
      coordinates.push([x + width, y, y + height - 1, -1]);
    });
  
    // x축을 기준으로 정렬한다.
    const sorted = mergeSort(coordinates, (c) => c[0]);
    // 좌표 평면을 좌측에서 우측으로 순회하면서 매좌표까지 사각형이 차지하는 y좌표를 저장한다.
    const height = Array(10000 + 1).fill(0);
    for (let y = sorted[0][1]; y <= sorted[0][2]; y++) height[y] = 1;
    let sum = 0;
    for (let i = 1; i < sorted.length; i++) {
      // 겹치는 부분을 제외하고 순수하게 높이만 구한다.
      const h = height.reduce((acc, cur) => acc + (cur === 0 ? 0 : 1), 0);
      const x2 = sorted[i][0];
      const x1 = sorted[i - 1][0];
      sum = sum + (x2 - x1) * h;
  
      const y1 = sorted[i][1];
      const y2 = sorted[i][2];
      // 사각형은 서로 겹칠 수 있으므로, 누적값을 저장해야 한다.
      for (let y = y1; y <= y2; y++) height[y] += sorted[i][3];
    }
    return sum;
  }
  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
*/

 

풀이코드 2:

const merge = function (left, right, comparator = (item) => item) {
  let merged = [];
  let leftIdx = 0,
    rightIdx = 0;
  const size = left.length + right.length;
  for (let i = 0; i < size; i++) {
    if (leftIdx >= left.length) {
      merged.push(right[rightIdx]);
      rightIdx++;
    } else if (rightIdx >= right.length || comparator(left[leftIdx]) <= comparator(right[rightIdx])) {  
      merged.push(left[leftIdx]);
      leftIdx++;
    } else {
      merged.push(right[rightIdx]);
      rightIdx++;
    }
  }
  return merged;
};

const mergeSort = function (arr, comparator) {
  const aux = (start, end) => {
    if (start >= end) return [arr[start]];
    const mid = Math.floor((start + end) / 2);
    const right = aux(start, mid);
    const left = aux(mid + 1, end);
    return merge(left, right, comparator);
  };
  return aux(0, arr.length - 1);
};

function shadowOfPapers(papers) {
  const coordinates = [];
  papers.forEach((p) => {
    const [x, y, width, height] = p;
    coordinates.push([x, y, y + height - 1, 1]);
    coordinates.push([x + width, y, y + height - 1, -1]);
  });

  const sorted = mergeSort(coordinates, (c) => c[0]);
  const height = Array(10000 + 1).fill(0);
  for (let y = sorted[0][1]; y <= sorted[0][2]; y++) {
    height[y] = 1;
  }
  let sum = 0;
  for (let i = 1; i < sorted.length; i++) {
    const x2 = sorted[i][0];
    const x1 = sorted[i - 1][0];
    const h = height.reduce((acc, cur) => acc + (cur === 0 ? 0 : 1), 0);
    sum += (x2 - x1) * h;
    for (let y = sorted[i][1]; y <= sorted[i][2]; y++) {
      height[y] += sorted[i][3];
    }
  }
  return sum;
}

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

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