백준 11501번 주식 파이썬 코드 + 풀이

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

11501번: 주식

for _ in range(int(input())):
    n = int(input())
    lists = list(map(int , input().split()))
    max_num = 0
    counter = 0
    for i in range(n-1,-1, -1) : #역순 인덱싱
        if lists[i] > max_num :
            max_num = lists[i]
        else :
            counter += max_num - lists[i]
    print(counter)

---

풀이

주가 계산 자체는 간단하다

해당 일자의 주가가 남은 일자 주가의 최댓값보다 작으면 무조건 사고

해당 일자의 주가가 최댓값이라면 지금까지 가지고 있던 주식을 모두 팔면 된다

 

문제는 주가를 앞에서 부터 읽을지 뒤에서 부터 읽을지가 중요한데

만약 앞에서부터 읽으면 계속해서 남은 일자들의 최댓값을 갱신해줘야 한다

남은 일자 중의 최댓값을 확인하려면 매번 주가를 추가할 때 마다 리스트를 새로 읽어와야 하며

이 말을 그 만큼 시간 복잡도가 늘어난다는 말이고 그러면 시간 초과가 발생한다

앞에서부터 읽는 경우를 여러가지 방법으로 구현해봤는데

정말 뭔 짓을 해도 시간 초과가 발생했다

 

그렇다면 뒤에서부터 읽어오면 어떨까?

남은 일자를 모두 읽어서 최댓값을 갱신할 필요가 없고

저장된 최댓값과 해당 날짜의 값만 비교해도 된다

해당 날짜의 값이 최댓값이라면 애초에 뒤에서 부터 읽어왔으므로 자연스럽게 해당 일자의 값이

남은 일자중에 최대가 되기 때문이다

이 방법을 사용하면 어렵지 않게 문제를 해결 할 수 있다