code signal - 32. absoluteValuesSumMinimization

Question

Given a sorted array of integers a, your task is to determine which element of a is closest to all other values of a. In other words, find the element x in a, which minimizes the following sum:

abs(a[0] - x) + abs(a[1] - x) + ... + abs(a[a.length - 1] - x)

(where abs denotes the absolute value)

If there are several possible answers, output the smallest one.

Example

• For a = [2, 4, 7], the output should be absoluteValuesSumMinimization(a) = 4.

  • for x = 2, the value will be abs(2 - 2) + abs(4 - 2) + abs(7 - 2) = 7.
  • for x = 4, the value will be abs(2 - 4) + abs(4 - 4) + abs(7 - 4) = 5.
  • for x = 7, the value will be abs(2 - 7) + abs(4 - 7) + abs(7 - 7) = 8.

  The lowest possible value is when x = 4, so the answer is 4.

• For a = [2, 3], the output should be absoluteValuesSumMinimization(a) = 2.

  • for x = 2, the value will be abs(2 - 2) + abs(3 - 2) = 1.
  • for x = 3, the value will be abs(2 - 3) + abs(3 - 3) = 1.

  Because there is a tie, the smallest x between x = 2 and x = 3 is the answer.
  

Input/Output

• [execution time limit] 4 seconds (py3)

• [input] array.integer a

  A non-empty array of integers, sorted in ascending order.

  Guaranteed constraints: 1 ≤ a.length ≤ 1000, -106 ≤ a[i] ≤ 106.

• [output] integer

  • An integer representing the element from a that minimizes the sum of its absolute differences with all other elements.

MY_ANSWER

def absoluteValuesSumMinimization(a):

    a_list = list(set(a))
    a_list.sort()
    diff_value = []
    answer = []

    for i in a_list:
        for j in a:
            diff_value.append(abs(i-j))

    while diff_value != []:
        answer.append(sum(diff_value[:len(a)]))
        del diff_value[:len(a)]

    for i in range(len(answer)):
        if answer[i] == min(answer):
            return a_list[i]

• 리스트 안의 원소 하나와 나머지 다른 원소들과 간격의 합을 비교하였을 때 가장 작은 간격의 합을 나타내는 값을 리턴한다. 가장 작은 간격을 가지는 원소가 2개일 경우, 둘 중에 크기가 작은 원소를 리턴한다.
• 먼저 하나의 기준 원소로 다른 원소들의 간격을 비교하는데 리스트에 있는 원소 갯수만큼 시행한다.
• diff_value 리스트에는 기준 원소를 기준으로 원소들 간의 간격을 비교한 것이 모두 포함되어 있기에 리스트에 있는 원소 길이만큼을 더해 원소 별 간격들의 합을 구한다.
• 마지막으로 최소 간격을 가지는 원소를 리턴해준다.

Best_ANSWER

def absoluteValuesSumMinimization(A):
    return A[(len(A)-1)//2]

• input이 sorted 된것을 이용, 가장 가운데 있는 원소가 다른 원소들 간의 간격에서 최소라는 것을 생각한다.
• my_answer는 지문그대로를 코드를 옮겼을 뿐, best_answer는 input 형태를 고려하여 좋은 코드 작성