Skyline Problem の解決方法

The Skyline Problem by using an iterative method

1. sorts the elements of a given array in ascending order.
2. Set the initial value of sum to 0.

3. Then use iterative methods：
   3.1 Find the smallest value array[0] in the array Because it has to be painted at least array[0] times.
   3.2 now sum += array[0]
   3.3 Set a new empty array
   3.4 Then, starting with the second element array[1] and ending with the last　element array[len(array)] in the array, insert the difference between these　values and the first element into the new empty array.
   3.5 Update the array： clear the array and assign the value of new array to
   original array
   3.6 Back to step 3.1 until the length of the array is 2

4. if the length of array is 2, sum += array[0] + difNum (difNum = array[1] - array[0])

5. return the sum

Code

def solution(A):
  # sorts the listA in a ascending order
  newA = sorted(A)
  return solution_help(newA)



def solution_help(array):
  # Set the initial value of sum to 0
  sum = 0
  if len(array) == 1:
    sum = array[0]
    return sum
  while len(array) > 2:
    min = array[0]
    sum += array[0]
    arraynew = []
    for i in range(1,len(array)):
      difNum = array[i] - array[0]
      arraynew.append(difNum)
    array = []
    array = arraynew

  if len(array) == 2:
    difNum = array[1] - array[0]
    sum += array[0] + difNum
  return sum

list1 = [1,3,6,4,5,1,1,1] 

print(solution(list1))  
#6