[LEET CODE] 121. Best Time to Buy and Sell Stock

# Problem

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0. Constraints: 1 <= prices.length <= 105 0 <= prices[i] <= 104

 

# My Answer

Time Limit Exceeded

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if prices == sorted(prices,reverse = True):
            return 0
        profit = 0
        for i in range(len(prices)-1): # 현재 값 이후에 나오는 값 중 가장 큰 값과의 차와 현재 profit 중 큰 값
            profit = max(max(prices[i+1:])-prices[i],profit) 
        return profit

 

# Solution 1 - 브루트 포스로 계산

Time Limit Exceeded

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_price = 0

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

        return max_price

 

# Solution 2 - 저점과 현재 값과의 차이를 계산

import sys

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize # 시스템의 최대값으로 초기값 설정

        # 최소값과 최대값 계속 갱신
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)

        return profit

최소값 계속 갱신하면서 최솟값 이후엔 가장 큰 값만 고려 

 

---

# 초기값 설정

어떤 값이 들어오든 바로 교체 가능하도록 

 

sys 모듈 이용

최소값 = 시스템의 최대값 (sys.maximize)

최대값 = 시스템의 최소값 (-sys.maximize)

 

float() 이용

mx = float('-inf')

mn = float('inf')

 

mn=999999와 같이 임의 설정 방법은 문제가 생길 수 있다.

 

코딩테스트의 경우

제약 조건이 있으면 그 기준에 맞춰서 지정