[LeetCode/Easy] 121. Best Time to Buy and Sell Stock

121. Best Time to Buy and Sell Stock

내 풀이 vs. 답안 풀이

---

	내 풀이	답안 풀이
prices 길이가 1일 때 return 0	if len(prices) == 1:     return 0 else:     for i in range(len(prices)):         # 이하 생략	max_profit = 0 for i in range(len(prices) - 1):     for j in range(len(prices))         # 이하 생략 return max_profit -> i는 마지막 원소를 돌지 않게끔 하면 if문으로 확인할 필요 없음
최대 profit을 구하는 방식	profits = [] profits.append(profit) return max(profits) -> max(), min() 없이 최대값, 최소값을 구할 때는 변수 하나 생성해서 비교한 후 해당 값을 계속 업데이트 해야 함. 리스트에 담으면 $O(n)$의 space complexity로 인해 Memory Limit 초과가 나올 수 있음.	max_profit = 0 if profit > max_profit: max_profit = profit return max_profit -> 구해야 하는 것이 2개일 때는 쉬운 예시를 들면서 둘 간의 관계나 숨겨진 조건을 찾아보자!

내 답안

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profits = []
        if len(prices) == 1:
            return 0
        else:
            for i in range(len(prices)):
                cur = prices[i]
                for j in range(i+1, len(prices)):
                    try:
                        right = prices[j]
                    except:
                        break
                    if right > cur:
                        profit = right - cur
                    else:
                        profit = 0
                    profits.append(profit)
            return max(profits)

012

문제 풀면서 작성한 메모

답안 예시

Approach 1: Brute Force

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                if profit > max_profit:
                    max_profit = profit
                    
        return max_profit

• Time complexity: $O(n^2)$ -> Time Limit Exceeded
• Space complexity: $O(1)$

Approach 2: One Pass

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for i in range(len(prices)):
            if prices[i] < min_price:
                min_price = prices[i]
            elif prices[i] - min_price > max_profit:
                max_profit = prices[i] - min_price
                
        return max_profit

• Time complexity: $O(n)$
• Space complexity: $O(1)$

개념 정리

---

없음