[문제]

평면 위에 N개의 직사각형이 놓여있습니다. 직사각형의 각 변은 x축, y축에 평행합니다. 각각의 직사각형은 왼쪽 아래 좌표(x1, y1)과 오른쪽 위 좌표 (x2, y2)를 가지며, (x1, y1, x2, y2)로 나타내고, 서로 겹쳐있을 수 있습니다. 이때 이 직사각형들이 차지하는 면적을 구하려고 합니다. 다음은 N = 5인 경우의 예시입니다.

위 그림에는 5개의 직사각형 (1, 1, 6, 5), (2, 0, 4, 2), (2, 4, 5, 7), (4, 3, 8, 6), (7, 5, 9, 7) 이 놓여있습니다. 이때 전체 직사각형이 덮고 있는 면적은 아래 그림의 검은 테두리 안쪽의 면적과 같습니다.

따라서 위 예시에서 5개의 직사각형이 덮고 있는 면적은 38이 됩니다.

평면 위에 놓여있는 직사각형들의 좌표가 매개변수 rectangles로 주어질 때, 직사각형들이 덮고 있는 면적의 넓이를 return하도록 solution 합수를 완성해 주세요.

제한사항
직사각형의 개수 N : 1 ≤ N ≤ 100,000
직사각형의 좌표 x1, y1, x2, y2 : 0 ≤ x1 < x2 ≤ 109 , 0 ≤ y1 < y2 ≤ 109
x1, y1, x2, y2는 정수

입출력 예

입출력 예 설명
입출력 예 #1
직사각형 (0, 1, 4, 4)가 차지하는 면적은 12이며, 직사각형 (3, 1, 5, 3)이 차지하는 면적은 4입니다. 두 직사각형의 겹치는 면적은 2 이기 때문에 전체 면적은 12 + 4 - 2 = 14입니다.

입출력 예 #2
문제의 예시와 같습니다.

[풀이]

function solution(rectangles) {
  var answer = 0;
  const area = [];
  let maxWidth = 0;
  let maxHeight = 0;
  const length = rectangles.length;
  let index = rectangles[0][1];
 
  // 가로, 세로 가장 마지막 값 구함
  rectangles.forEach(arr => {
    maxWidth = arr[2] > maxWidth ? arr[2] : maxWidth;
    maxHeight = arr[3] > maxHeight ? arr[3] : maxHeight;
  });
 
  // 위에서 구한 값으로 배열에 0을 할당해서 채움
  for(let i = 0; i < maxHeight; i++) {
    area.push(new Array(maxWidth).fill(0));
  }

  for(let i = 0; i < length; i++) {
    if(rectangles[i][1] <= index && index < rectangles[i][3]) {
      area[index].fill(1, rectangles[i][0], rectangles[i][2]);
      index += 1;
      i -= 1;
    }
    else {
      index = i + 1 < length ? rectangles[i + 1][1] : null;
    }
  }

  for(let arr of area) {
      answer += arr.filter(num => num === 1).length;
  }

  return answer;
}

우선 사각형 전체가 그려질 면적을 구하기 위해 가로, 세로 가장 마지막 위치를 구함.
그리고 그만큼 배열에 크기를 할당해서 0으로 채움.
이제 rectangles를 돌면서 사각형이 그려질 곳을 1로 채워 나가고
마지막에 1의 개수를 구함.
그런데 시간초과가 뜨고 테스트케이스 두개는 (signal: aborted (core dumped))가 뜨는데
메모리관련 에러라고 하는거 같은데 아마도 처음에 배열에 0을 할당할 때
크기가 너무 커서 문제가 되는듯.
전반적으로 코드 수정이 필요해 보임.