[Python] 백준 #11501- 주식

문제

---

 

11501번: 주식

코드

---

My answer(시간초과)

import sys
input=sys.stdin.readline

n=int(input())

for i in range(n):
    day=int(input())
    price=list(map(int,input().split()))
    profit,num=0,0
    for j in range(len(price)):
        if(price[j]==max(price[j:])):
            profit+=(num*price[j])
            num=0
        else:
            profit-=price[j]
            num+=1
    print(profit)

 

Another answer

import sys
input=sys.stdin.readline

n=int(input())

for i in range(n):
    day=int(input())
    price=list(map(int,input().split()))
    profit=0
    max_p=0
    for j in range(len(price)-1,-1,-1):
        if(price[j]>max_p):
            max_p=price[j]
        else:
            profit+=max_p-price[j]
    print(profit)

for i in range(n):
    day=int(input())
    price=list(map(int,input().split()))
    price.reverse()
    max = price[0]
    sum = 0

    for j in range(1, day):
        if max < price[j]:
            max = price[j]
            continue
        sum += max - price[j]
    print(sum)

풀이

---

우선 문제의 아이디어 자체는 구하기 쉬웠던 문제이다. 

가격이 낮을 때 사서 가장 비쌀 때 팔면 최대의 이익을 얻을 수 있었다.

그래서 내 코드를 보면, max(price[i:])가 오늘을 포함한 이후로 부터 가장 가격이 크면 현재 보유한 주식개수만큼 최고가에 팔고, 오늘보다 비싼날이 있으면 우선 주식을 사는 방식으로 작성하였다. 코드 자체는 맞았지만 max를 계속 계산하게되면서 시간초과가 발생하였다.

이에 다른 분들의 코드를 참조하니 해결법은 뒤에서부터 문제를 푸는 것이었다. 처음에는 뒤에서 풀면 뭐가 다르지? 생각했었는데 간단하게 이해했다.

 

1. 내 코드는 오늘이 최고가가 아니면, 주식을 사고(주식 개수를 누적해줘야함) 최고가인 날 그 최고가에 현재 보유주식을 파는 방식 -> 오늘을 포함한 다음날들중 최고가를 매번 확인해줘야 함.

EX) 3,5,9 입력 

1. 3,5,9 중 최고가 9이므로 주식을 하나 사고(count+=1), 보유자산에서 3을 빼줌(profit-=3)
2. 5,9 중 최고가 9이므로 주식을 하나 더 사고(count+=1) , 보유자산에서 5를 빼줌 (profit-=5)
3. 9중 최고가 9이므로, 보유주식(현재 2)을 모두 9에 팔고 보유자산에 9*count(2)를 더해줌. 

2. 첫번째 다른 코드 

최고가를 0으로 초기화하고, 뒤에서부터 돌면서 가격이 오늘 가격이 최고가보다 크면 최고가를 갱신 후 pass 최고가보다 작으면 오늘가격에서 최고가에서 오늘가격을 뺌.

EX) 입력이 3,5,9 이면 최고값을 0으로 초기화하고 9,5,3순서로 돌기 시작함. 

1. 최고가를 0으로 갱신, 리스트를 역순으로 돌림 9,5,3
2. 9>0(최고가) 이므로 최고가 9로 갱신
3. 9(최고가)>5 이므로 9-5=4 (역방향으로 하기 때문에 바로 빼면됨, 원래는 5에 사서 9에 판다는 의미)
4. 9(최고가)>3 이므로 9-3=6 (위와 동일)

3. 두번째 다른 코드

위와 동일한 방법이나 단순 max를 초기값(입력값의 역순의 첫번째 값)을 최대로 설정하여 진행 

 

최종적으로 역순으로 돌면서 이익계산을 바로바로 진행하는 방식으로 하면 max()함수를 계속하여 쓰지않고 진행하므로 시간초과가 발생하지 않았다.