백준 문제풀이 - 11501 번

링크 -> https://www.acmicpc.net/problem/11501

1. 요약 및 풀이방법

주식 가격을 안다고 가정 했을 때,
최대 수익을 낼 수 있도록 하는 코드를 작성하는 문제입니다.

문제 자체를 해결하는 방법은 매우 간단합니다.
가격이 오르고 내리는 것을 알기 때문에,
날짜 흐름에 따라 오르기 전에 사서 높은 값에 파는것을 반복하면 됩니다.

이렇게 앞에서부터 진행하면 쭉 사고, 현재 날짜로부터 max 위치를 찾아서
그 전까지 모두 사고, 높을 때 파는것을 반복합니다.

그런데 최악의 경우,
가격이 떨어지기만 한다면 모든 날짜로부터 남은 날까지 구간 안의 max 위치를 매번 찾아야 하고,
이는 O(N^2) 의 시간 복잡도를 갖습니다.

따라서 이렇게 앞에서부터 푸는게 아닌,
뒤에서부터 앞으로 진행하면 높은 가격을 알기 때문에
현재 가격보다 낮으면 차액을 누적하고,
더 높은 가격을 만나면 새로 그 시점부터 다시 새로운 기준으로 계산하면 O(N)의 시간복잡도로 해결 할 수 있습니다.

2. Code

import sys

def main():
    T = int(input())
    for _ in range(T):
        N = int(sys.stdin.readline().rstrip())
        stocks = list(map(int, sys.stdin.readline().rstrip().split()))
        value = 0

        max_value = 0
        for stock in stocks[::-1]:
            max_value = max(max_value, stock)
            value += max_value - stock
        print(value)

if __name__ == "__main__":
    main()

3. 학습 내용

처음엔 앞에서부터 계산하면서 시간초과를 많이 겪었습니다.
해결하기 위해 python 에서 사용하는 여러 기본 메소드나 연산자의 시간 복잡도를 참고했지만 해결 되지 않았습니다.

이렇게 거꾸로 푼다는 간단한 아이디어 전환만으로
시간도 줄이고, 코드의 길이도 훨씬 짧아짐을 보았습니다.

4. 결과