백준 / 실버 4 / 13458 ATM / Python [정렬]

sum

이론적으로 O(N)복잡도인데 체감은 O(1)이었다.
내부 동작은 공식 레퍼런스에 안나와 있다..
MAP-REDUCE로 최적화가 잘 돼있나..?

O(N^2) : 92ms

O(N) : 44ms

import sys
input = sys.stdin.readline

n = int(input())
p = sorted(list(map(int,input().split())))
print(sum(p[i] * (n-i) for i in range(n)))

map then sum : 44ms

import sys
input=sys.stdin.readline

n=int(input())
p=sorted(list(map(int,input().split())))
print(sum(map(lambda i: p[i]*(n-i), range(n))))

sum then sum : 44ms

import sys
input = sys.stdin.readline

N = int(input())
P = sorted(list(map(int, input().split())))
print(sum(sum(P[:i+1]) for i in range(N)))

리스트 슬라이싱으로 인한 복사 비용도 있는데도 차이 안났다.