주식을 사고팔기 가장 좋은 시점

한 번의 거래로 낼 수 있는 최대 이익을 산출하라.

 

input : [7,1,5,3,6,4]
output : 5
>> 1 일 때 사서 6일 때 팔면 5의 이익을 얻는다.

 

해당 문제는 가장 저점일 때 구매하여 고점일 때 판매하면 되는 것이다.

 

그렇다면 우리는 가장 간단하게도 이중 for문을 돌려 비교하여 사고팔고를 반복하여 결과를 산출 할 수 있다.

하지만 그럴경우 O(n^2) 의 많은 실행시간을 허비한다.

 

def max_profit(prices):
    profit = 0

    for i, price in enumerate(prices):
        for j in range(i, len(prices)):
        	max_price = max(prices[j] - price, max_price)

    return profit

 

좀 더 효율적인 방법을 생각해봐야 할것이다.

 

이중 for문을 사용하지 않고 한 번의 for문을 사용하여 구하기 위해서 둬야할 체크포인트는 무엇일까?

 

한 번의 for문 시 최솟값을 알고 앞으로 나오는 수와 비교하였을 시 가장 큰 차이가 나는 경우를 뽑아야한다.

 

1. 최솟값

 

리스트의 첫 번째가 최솟값이 된다고 단언 할 수 없기에 이중  for문을 사용하지 않기 위해서 sys.maxsize를 사용하여 최솟값을 구한다. sys.maxsize는 파이썬의 정수는 가장 큰 수이다.

이를 이용하여 minNum = sys.maxsize 이고 앞으로 나오는 수가 더 작을 시 minNum으로 하는 코드를 짠다.

minNum = sysMaxsize #파이썬의 가장 큰 수
minNum = min(minNum, 리스트의 값)

 

2. 최대 이익산출

최대 이익을 구하기 위해서는 앞으로 나오는 값에 앞서 구한 최솟값 뺀 값 중 가장 큰 값을 구해야한다.

최대값은 항상 0보다는 커야하기에 그리고 input이 [] 빈 리스트의 경우 -sys.maxsize 가 리턴이 될수 있기에 0으로 설정을 해 코드를 작업한다. (개인적으로는 input을 안 넣는 경우는 없기에 알고리즘 적인 생각으로는 -sys.maxsize를 설정하는게 맞다고 생각한다.)

 

profit = -sys.maxsize #파이썬의 가장 작은 정수
profit = max(profit, 리스트의 값 - minNum)

리스트가  for문을 돌면서 각각의 값에 최솟값인 minNum을 빼서 차이를 비교한다. 

 

최종 코드

def max_profit(prices):
    profit = -sys.maxsize
    min_price = sys.maxsize

    for list_value in prices:
        min_price = min(min_price, list_value)
        profit = max(profit, list_value-min_price)

    return profit