11501_주식

제일 막바지에 풀어서 반쯤 정신 놓은 채로 풀어서 코드를 효율적으로 짜지는 못했다. 앞선 문제에서 문자열 처리를 하느라 에너지 소모가 더 컸던 것 같다.
이 문제의 핵심은 n^2의 복잡도를 n으로 바꾸는 것이다.
문제 자체는 어렵지 않은데 저 방법을 떠올리는 것이 핵심이었다.

방법은 받은 주식 가격의 리스트에서 뒤에서부터 크기를 비교하며 최댓값을 저장하는 리스트를 따로 만든 다음에, 최대값 - 주식가격을 하는 것

핵심은 뒤에서 부터 비교하는 것이다.
앞에서부터 비교하면 n^2의 복잡도로 비교할 수 밖에 없기 때문이다.

가 있다고 치면

앞에서부터 탐색하면 다음과 같이 N^2로 탐색을 해야한다.
하지만 뒤에서부터 탐색하면

다음과 같이 탐색하며 따로 인덱스 값을 리스트에 저장하면 N의 복잡도로 탐색할 수 있다.

k =  int(input())
for j in range(k):
    n = int(input())
    stock = list(map(int, input().split()))

    max = 0
    result = 0
    max = stock[-1]
    max_list = []
    for i in reversed(range(len(stock))):
        if max < stock[i]:
            max = stock[i]
            max_list.append(i)
            
    max_list.sort()
    max_list.append(len(stock)-1)
    
    sub = stock[max_list[0]]
    
    result = []
    index = max_list[0]
    for i in range(len(stock)):
        result.append(stock[i] - sub)
        if i == index:
            if len(max_list) != 0:
                del max_list[0]
                if len(max_list) != 0:
                    index = max_list[0]
                    sub = stock[index]
    
    ans = 0
    for i in range(len(result)):
        ans += result[i]
    print(abs(ans))
   

다음은 N^2의 복잡도로 탐색한 코드이다. 훨씬 짧고 간결하지만 효율적이지는 못하다.

k =  int(input())
for j in range(k):
    n = int(input())
    stock = list(map(int, input().split()))

    max = 0
    result = 0
    
    for i in range(len(stock)):
        max = stock[i]        
        for w in range(i,len(stock)):
            if stock[w] > max:
                max = stock[w]
        result += (max - stock[i])
    print(result)