[컴][알고리즘] skyline problem

divide and conquer /


작성중...

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 가 좋은지 더 높은지 확인한다.

빌딩이 끝나는 곳에 해당하는 x 에서는 height 가 0 이기 때문에, x 위치에서 가장높은 height 만 선택하면 된다.(max(h1, h2))

python code

source from : ref. 1

def 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

See Also

1. [컴][알고리즘] Merge sort

Reference

1. performance - Python program to solve the "skyline problem" - Code Review Stack Exchange