[알고리즘/그리디] 11501번 : 주식 - python

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

11501번: 주식

 

---

• 문제
• 소요시간: 23분 12초

---

• 설계하기(접근방법) 

1. 입력받기

문제의 조건대로 입력받는다

 

2. 구현하기

먼저 주가 리스트의 가장 1번째 원소가 최댓값인 경우

주식을 살 필요가 없으니 바로 0을 출력해준다

 

아니라면

리스트의 최대값을 기준으로

차액을 더해 나가고

최대값을 만나면, 그 다음 인덱스부터 끝까지의 최대값을 새로 구한다

이 새로운 최대값의 차액을 이익으로 더해나간다

 

+ 추가

이 문제같은 경우

이 문제는 최대값이 갱신됨에 따라, 그 뒤의 새로운 최대값을 찾는데 소요가 든다

 

 

뒤에서부터 리스트를 순회하면 더 빠르게 통과할 수 있다.

뒤의 최대값은 앞의 최대값에 영향을 받지 않기 때문이다

 

앞의 최대값이 뒤의 최대값보다 작다면, 최대값이 갱신될리가 없고

뒤의 최대값보다 크다면 이미 그 시점에서 주식을 판매했을테니 뒤의 이익에는 영향을 미치지 않는다

 

따라서 이 문제를 설계할 때, 뒤에서부터 최대값을 검사하면서

최대값보다 작은 원소들의 차액을 더해나가고,

최대값보다 큰 원소가 나타나면 갱신해주면 된다

 

 

 

 

 

3. 출력하기

총 번 돈을 출력한다

 

 

---

• 코드(출력)

test = int(input())
for i in range(test):
    day = int(input())
    price_list = list(map(int, input().split()))
    max_price = max(price_list)

    profit = 0
    if price_list[0] == max_price:
        print(0)
        continue
    else:
        j = 0
        while j < day:
            if price_list[j] < max_price:
                profit += (max_price - price_list[j])
            if price_list[j] == max_price and j < day - 1:
                max_price = max(price_list[j + 1:])
            j += 1
        print(profit)

---

• 얻어갈 부분

1. 원래는 시간초과가 걸릴 뻔했지만, 가장 시간이 많이 드는 케이스를 조건문으로 처리해서 시간을 절약했다. 문제가 시간초과 될 것 같으면 뒤에서부터 순회하는 방법을 떠올려보자