백준 11501번 주식 (Python)

문제

홍준이는 요즘 주식에 빠져있다. 미래를 내다보는 눈이 뛰어나, 주가를 예상하고 언제나 그게 맞아 떨어진다.(부럽다)

매일 그는 세 가지 중 한 행동을 한다.

1. 산다.

2. 판다.

3. 아무것도 안한다.

홍준이의 최대 이익이 얼마나 되는지 계산해주자.

풀이

첫번째로는 스택을 이용해서 풀었다. top의 값보다 작은 노드를 발견하면 (val[top] - val[current])값을 profit이라는 변수에 더한다.

top의 값보다 큰 노드를 발견하면 그 노드 인덱스 이후 노드들을 모두 제거한다.

for _ in range(int(input())) :
    
    day = int(input())
    info = list(map(int, input().split()))
 
    profit = 0
 
    cur = len(info) - 2
 
    while True :
        # 현재 노드가 top보다 작으면 이익.
        if info[-1] > info[cur] :
            profit += info[-1] - info[cur]
        # 현재 노드가 top보다 크거나 같으면 스택에서 제외.
        else : 
            info = info[:cur+1]
            
        cur -= 1
 
        if cur == -1 :
            break 
 
    print(profit)

사실 굳이 저렇게 풀 필요는 없다.

def stock(n, l) :
    
    cMax = l[n-1]
    profit = 0
 
    for i in range(n-2, -1, -1) :
 
        if cMax >= l[i] :
            profit += cMax - l[i]
        else :
            cMax = l[i]
 
    return profit
 
for _ in range(int(input())) :
 
    n = int(input())
    l = list(map(int, input().split()))
 
    print(stock(n, l))

https://www.acmicpc.net/problem/11501