[Cos Pro 1급] 1차 10번 - 주식 매수 매도

문제

지난 연속된 n일 동안의 주식 가격이 순서대로 들어있는 리스트가 있습니다.  이 때, 다음 규칙에 따라 주식을 사고 팔았을 때의 최대 수익을 구하려 합니다.  

 

n일 동안 주식을 단 한 번 살 수 있습니다.  n일 동안 주식을 단 한 번 팔 수 있습니다.  주식을 산 날에 바로 팔 수는 없으며, 최소 하루가 지나야 팔 수 있습니다.  적어도 한 번은 주식을 사야하며, 한 번은 팔아야 합니다.

 

주식을 팔 때는 반드시 이전에 주식을 샀어야 하며, 최대 수익은 양수가 아닐 수도 있습니다.

 

연속된 n 일 동안의 주식 가격이 순서대로 들어있는 리스트 prices가 매개변수로 주어질 때, 주식을 규칙에 맞게 한 번만 사고 팔았을 때 얻을 수 있는 최대 수익을 return 하도록 solution 함수를 작성했습니다. 그러나, 코드 일부분이 잘못 되어있기  때문에, 코드가 올바르게 동작하지 않습니다.

 

 

매개변수 설명

연속된 n 일 동안의 주식 가격이 순서대로 들어있는 리스트 prices가

solution 함수의 매개변수로 주어집니다.

* prices의  길이는 2 이상 1,000,000 이하입니다.

* prices의 각 원소는 1 이상 1,000 이하의 자연수입니다.

 

return 값 설명

주식을 규칙에 맞게 한 번만 사고팔았을 때 얻을 수 있는 최대 수익을 return 해주세요.

 

예시

prices	return
[1,2,3]	2
[3,1]	-2

 

 

예시 설명

예시 #1

연속된 3일의 주가가 차례로 [1, 2, 3] 이며,

첫째 날에 주식을 사서 셋째 날에 팔면 수익은 2이고, 이때가 최대입니다.

예시 #2

문제에서 설명한 것처럼 무조건 한 번은 매수하고, 한 번은 매도해야 합니다.

첫째 날에 매수하여 둘째 날에 매도하는 방법 밖에 없기에 수익은 -2, 즉 2만큼 손실을 보게 됩니다.

 

 

Python

O(n^2)

def solution(price):
    ans = []
    for i in range(len(price)-1):
        for j in range( i+1, len(price) ):
            ans.append( -price[i] + price[j] )
    #Brute Force: 싹 다 해본다
    #모든 경우의 수를 다 확인해본
    return max(ans)

print( solution([1,2,3]) )
print( solution([3,1]) )

 

O(n)

def solution(price):
    max_profit = price[1] - price[0] 
    min_stock = min(price[0], price[1]) #현재까지의 최소 주식 가격
    
    for i in range(2, len(price)):
    	max_profit = max(max_profit, price[i] - min_stock)
        min_stock = min(min_stock, price[i])

print( solution([1,2,3]) )
print( solution([3,1]) )