[LeetCode]121.주식을 사고팔기 가장 좋은 시점(Best Time to Buy and Sell Stock)

[문제]

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

 

·입력

[7,1,5,3,6,4]

·출력

5

·설명

1일 때 사서 6일 때 팔면 5의 이익을 얻는다.

 

[처음 작성한 코드]

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res=0
    
        for i,price in enumerate(prices):
    	    for j in range(i,len(prices)):
        	    res=max(prices[j]-price,res)
        return res

처음 떠오르는게 브루트 포스 방법이어서 작성해보았다. 당연히 타임아웃이다.

1행 리스트 문제를 풀 때 for문이 두개 이상 나오면 대부분 타임아웃이 되는 것 같다.

 

참고로 시간을 줄이기 위해서 enumerate를 애용하는 것이 좋다.

 

[수정 코드]

 

for문을 하나만 사용하도록 수정했다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
      profit=0
      min_val=sys.maxsize

      for p in prices:
        min_val=min(min_val,p)
        profit=max(profit,p-min_val)
      return profit

p에 p 이전 시점에 나온 최소값을 뺀 뒤 그 중 가장 큰 값이 가장 큰 이득이니까 위 코드로 해결이 가능하다. 

 

임의의 최소값, 최대값을 설정할 때, min_val=-9999999 이렇게 정의하게 되면 문제가 발생할 수 있다. 위 코드와 같이 sys.minsize, sys.maxsize를 사용하는 것을 추천한다.