Algorithm/백준
[Python] 11501 주식
내영잉
2023. 2. 16. 17:37
1. 문제 📚
https://www.acmicpc.net/problem/11501
11501번: 주식
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타
www.acmicpc.net
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)