백준 2399 파이썬 코드 답안

문제

수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.

즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.

입력

첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.

출력

첫째 줄에 답을 출력한다.

문제풀이

나는 다음과 같은 아이디어로 시간을 단축해서 풀었다고 생각을 했는데, 다른 분들 답안 제출하신 것들을 보니 O(n) 혹은 O(nlogn) 수준으로 시간복잡도를 줄일 수 있을 것으로 보인다. 내가 푼 방법은 굉장히 단순했는데, 아이디어는 이렇다

((a1-a2) + (a1-a3) + (a1-a4) + (a1-a5))*2를 할 경우, a2,a3,a4,a5에서 거리 연산을 진행할 때 다시 a1을 돌아보지 않아도 된다는 점을 이용했다. 더 설명할 것이 없어 아래에 코드를 첨부한다.

import sys
n = int(sys.stdin.readline().rstrip())
my_list = list(map(int,sys.stdin.readline().split()))

my_sum = 0
for i in range(len(my_list)) :
    temp = 0
    for j in range(i,len(my_list)) :
        temp += abs(my_list[i] - my_list[j])
    temp = temp*2
    my_sum += temp

print(my_sum)