1859. 백만장자 프로젝트

변경 전 

def earn(a,b=[]):
    earning = 0
    for i in range(a):
        maxx = max(b[i:])
        if maxx != b[i]: earning = earning + (maxx - b[i])
    return earning
    
    
t = int(input())
ans = []
for i in range(t):
    case = int(input())
    lst = list(map(int,input().split()))
    earning = earn(case,lst)
    ans.append(earning)
    
for j in range(t):
    print("#%d" % (j+1), ans[j])

 

시간 초과가 떠서 코드를 일부 수정

 

 

변경 후

t = int(input())
ans = []
for i in range(t):
    case = int(input())
    lst = list(map(int,input().split()))
    earning = 0
    maxx = lst[case-1]

    for j in range((case-1),0,-1):
        if maxx > lst[j-1]:
            earning = earning + (maxx - lst[j-1])
        else: maxx = lst[j-1]
    ans.append(earning)

for k in range(t):
    print("#%d" % (k+1), ans[k])
 

뒤에서부터 검색하면 max를 한번 돌때마다 전체를 검색할 필요가 없어짐