Golang 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 타입을 리턴해야 합니다.
  
  

입출력 예시

result := shadowOfPapers([][]int{{0, 1, 4, 4}})
fmt.Println(result) // --> 16

result = shadowOfPapers([][]int{{0, 0, 4, 4}, {2, 1, 2, 6}, {1, 5, 5, 3}, {2, 2, 3, 3}})
fmt.Println(result) // --> 36

 

go 소스코드

package main

import "fmt"

func merge(left [][]int, right [][]int, comparator func(item []int) int) [][]int {
	merged := make([][]int, 0)
	leftIdx := 0
	rightIdx := 0
	size := len(left) + len(right)

	for i := 0; i < size; i++ {
		if leftIdx >= len(left) {
			merged = append(merged, right[rightIdx])
			rightIdx++
		} else if rightIdx >= len(right) || comparator(left[leftIdx]) <= comparator(right[rightIdx]) {
			merged = append(merged, left[leftIdx])
			leftIdx++
		} else {
			merged = append(merged, right[rightIdx])
			rightIdx++
		}
	}
	return merged
}

func mergeSort(arr [][]int, comparator func(item []int) int) [][]int {
	var aux func(start, end int) [][]int
	aux = func(start, end int) [][]int {
		if start >= end {
			return [][]int{arr[start]}
		}
		mid := (start + end) / 2
		right := aux(start, mid)
		left := aux(mid+1, end)
		return merge(left, right, comparator)
	}
	return aux(0, len(arr)-1)
}

func shadowOfPapers(papers [][]int) int {
	coordinates := make([][]int, 0)

	for _, p := range papers {
		x, y, width, height := p[0], p[1], p[2], p[3]
		coordinates = append(coordinates, []int{x, y, y + height - 1, 1})
		coordinates = append(coordinates, []int{x + width, y, y + height - 1, -1})
	}

	comparator := func(c []int) int {
		return c[0]
	}

	sorted := mergeSort(coordinates, comparator)
	height := make([]int, 10000+1)

	for y := sorted[0][1]; y <= sorted[0][2]; y++ {
		height[y] = 1
	}

	sum := 0

	for i := 1; i < len(sorted); i++ {
		h := 0
		for _, v := range height {
			if v != 0 {
				h++
			}
		}
		x2, x1 := sorted[i][0], sorted[i-1][0]
		sum = sum + (x2-x1)*h

		y1, y2 := sorted[i][1], sorted[i][2]

		for y := y1; y <= y2; y++ {
			height[y] += sorted[i][3]
		}
	}
	return sum
}

func main() {
	result := shadowOfPapers([][]int{{0, 1, 4, 4}})
	fmt.Println(result) // --> 16

	result = shadowOfPapers([][]int{{0, 0, 4, 4}, {2, 1, 2, 6}, {1, 5, 5, 3}, {2, 2, 3, 3}})
	fmt.Println(result) // --> 36
}