Algorithm problem-43

1. 문제

• 직사각형 정보를 주고, 이 직사각형들의 총 면적을 리턴
• 겹치는 부분도 존재, 중복값은 X, [x좌표, y좌표, width, height] 값
• 스위핑 알고리즘(sweeping)을 이해하고 풀어야 한다고 함

2. 시도

• 직사각형 넓이합 구하기
• 라인스위핑에서 2차원 스위핑으로 전환 내용 정리된 블로그
• 모든 면적을 더하고 겹치는 면적을 구해 빼주고 하는 식의 풀이는 불가
• 스위핑 알고리즘의 이해가 필요
• 정렬된 순서대로 처리되는 이벤트의 집합으로 문제를 모델링하는 알고리즘
• 대부분의 블로깅 설명글은 라인 스위핑을 기준으로 하고 있음
• 이걸 2차원으로 넘어가면, 라인 스위핑을 최대 좌표까지 해주는 방식으로
• 1차원 라인 스위핑한 값을 누적시켜서 값을 구하면 될 것으로 예상됨
• 최소 좌표에서 최대 좌표까지에서 값이 있는 부분만 탐색해서 카운트하면 되지 않을까
• 예로, [0,0]에서 [6,6]까지의 최소, 최대 좌표를 놓고, 그 안에서 직사각형 좌표가
• 포함되어진 값을 찾으면서 있으면 카운팅하고, 없으면 지나가는 식으로 구현
• 탐색은 1차원 값의 최소부터 최대까지 탐색하고
• 그 결과를 누적시켜가면서 다음 1차원으로 이동, 최대 1차원까지 탐색하고 나면
• 누적된 결과를 리턴하면 되지 않을까

3. 수도코드

// 누적값을 더해줄 결과값 변수 선언

// 각 직사각형의 좌표값을 1차원 단위로 좌표값만 저장하고
// 최소 좌표부터 최대 좌표까지 모두 만들어서 저장해놓고

// 그 좌표들을 토대로 탐색을 시키면서 각 1차원당 값이 있는 부분만 카운팅하고
// 각 1차원의 카운팅이 끝나면 그 값을 누적값에 더해서 갱신하고
// 마지막 1차원까지 카운팅하고 난 후 마지막 값까지 갱신
// 저장된 누적값을 리턴시키면 되지 않겠나

4. 레퍼런스