작성중...
skyline problem
merge sort 와 비슷한방법으로 해결한다.(divide & conquer)merge sort 가 값을 만들어가는 모양처럼, array 가 있으면 일단 개개별로 분할될 때까지 내려가고, 그 개개의 값들을 merge 하면서 값을 처리한다.(Merge sort gif 참고)
이 문제에서는 x 를 다시 정렬할 필요가 있다. 아래 그림처럼 값을 새로운 모양으로 바꾸면서, 정렬이 안된 상태가 되기 때문이다. 그러므로 이런 merge sort 방식이 잘 어울린다.
merge 부분
들어온 input 에 대해서 length 가 1일때(base condition)"merge 할때 최종적으로 표현하려는 모양"을 return 한다.
여기서는
[[left, height], [left2, hegith2], ...] 이런 모양이다.핵심은 두개의 배열을 돌면서 하나의 배열이 끝날때까지만 돈다.
그러면서 필요한 처리를 하고, 그 이후의 배열의 원소는 전부 append 한다.
element 단위에서부터 이 작업을 하기에 남아서 뒤에 붙이게 되는 값들은 전부 정렬이 된 이후의 값들이다.
while i < len(arr1) and j < len(arr2): ... i++ j++ res.extend(arr1[i:]) res.extend(arr2[j:])
- 여기서 계속해서 x 를 움직이고,
- x 에 해당하는 height 를 비교한다.
- merge 가 되면서, x 는 정렬이 되어 간다.
- 그러면서 x 지점의 height 가 좋은지 더 높은지 확인한다.
max(h1, h2)) python code
source from : ref. 1def skyline(buildings):
# building = [[left, right, height], [2, 9, 10], ...]
if not buildings:
return []
if len(buildings) == 1:
# [[left, height], ...]
return [[buildings[0][0], buildings[0][2]], [buildings[0][1], 0]]
mid = len(buildings) // 2
left = skyline(buildings[:mid])
right = skyline(buildings[mid:])
return merge(left, right)
def merge(left, right):
h1, h2, hcurrent = 0, 0, 0
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
x0 = left[i][0]
x1 = right[j][0]
if left[i][0] < right[j][0]:
# 현재의 x 에 해당하는 h 를 선택한다.
h1 = left[i][1]
curX = left[i][0]
i += 1
elif right[j][0] < left[i][0]:
h2 = right[j][1]
curX = right[j][0]
j += 1
else:
h1 = left[i][1]
h2 = right[j][1]
curX = right[j][0]
i += 1
j += 1
# 현재의 h 는 h1, h2 중 하나이다. 그중에 큰 값을 선택한다.
# x 가 변하면, h 도 같이 변한다.
# 건물이 끝나는 x 에선 h가 0 이 된다.
if max(h1, h2) != hcurrent:
hcurrent = max(h1, h2)
result.append([curX, hcurrent])
result.extend(right[j:])
result.extend(left[i:])
return result
