📚 11501 - 주식

주식

이해

시간 제한이 5초, N이 1000000이므로 O(N^2)으로 풀면 안된다.
이중 for문으로 풀었는데 시간 초과 발생

그래서 다른 방법으로 뒤에서부터 검색하면서

• 현재 최대값보다 현재 인덱스 데이터가 더 크다면, 교체
• 아니라면, 이익 += (현재 최대값 - 현재 인덱스 데이터)

를 해준다.

소스

기존 시간 초과 소스 O(N^2)

import sys  
  
read = sys.stdin.readline  
  
t = int(read())  
  
for i in range(t):  
    n = int(read())  
    arr = list(map(int, read().split()))  
    answer = 0  
  
    for j in range(len(arr)-1):  
        afterjMAXDATA = max(arr[j+1:])  
        if arr[j] < afterjMAXDATA:  
            answer += afterjMAXDATA - arr[j]  
  
    print(answer)

O(N)으로 해결한 소스

import sys  
  
read = sys.stdin.readline  
t = int(read())  
  
for i in range(t):  
    n = int(read())  
    arr = list(map(int, read().split()))  
    answer = 0  
    afterMAXDATA = arr[-1]  
    for j in range(len(arr)-1, -1, -1):  
        if afterMAXDATA < arr[j]:  
            afterMAXDATA = arr[j]  
        else:  
            answer += (afterMAXDATA - arr[j])  
    print(answer)