[Python] 11501 주식

1. 문제 📚

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

11501번: 주식

2. 입출력 예 📋

3. 알고리즘 ✅

입력값이 큰 것을 보고 그리디인가 dp인가 생각해보다가 제일 큰 값에 팔면 최대 이익이 나오므로 -> 그리디 라고 생각하였다

처음엔 앞에서부터 차근차근 순회해가면서 하는 로직으로 짰지만 80퍼쯤에서 시간초과가 났다.

앞에서 순회하게 되면 리스트를 잘라주는 작업을 계속해주어야했다.

 

왜냐면 7, 6, 9, 1, 6 이라면 7, 6 은 9에 팔아야하고, 1은 6에 팔아야 최대 이익이기 때문에

list에서 최대이익 이후 숫자면 최대이익을 바꿔줘야하는 작업을 해야하기때문이다

 

아래는 시간초과난 코드이다 아마 max와 index 과정에서 for문을 한 번 더 돌기때문인거같다

import sys

input = sys.stdin.readline

T = int(input().strip())
answer_list = []
for i in range(T):
    N = int(input().strip())
    cost = list(map(int, input().strip().split()))
    max_cost = max(cost)
    max_index = cost.index(max_cost)

    answer = 0
    for j in range(N):
        if max_index == j and j+1 < len(cost):
            max_cost = max(cost[j+1:])
            max_index = cost[j+1:].index(max_cost) + (j + 1)

            continue
            
        if max_cost > cost[j] and max_index > j:
            answer += max_cost - cost[j]

    answer_list.append(answer)

for i in answer_list:
    print(i)

 

그래서 반대로 뒤로 가면서 순회하는 로직으로 변경하였다.

 

최대 이익을 맨 마지막 숫자로 두고

target이라는 index숫자를 두어 최대이익보다 target값이 크다면 최대이익을 target값으로 바꿔준다.

만약 작다면, 최대 이익에 팔아 이익을 구해주었다

4. 소스코드 💻

import sys

input = sys.stdin.readline

T = int(input().strip())
answer_list = []
for i in range(T):
    N = int(input().strip())
    cost = list(map(int, input().strip().split()))

    answer = 0
    
    # 마지막 숫자
    max_profit = cost[-1]
    target = N - 1

    while True:
        if target == -1:
            break

        if max_profit > cost[target]:
            answer += max_profit - cost[target]

        elif max_profit < cost[target]:
            max_profit = cost[target]

        target -= 1

    answer_list.append(answer)

for i in answer_list:
    print(i)