[LeetCode] 121번 (Python)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

 

1번 시도 ->  잘 돌아가는가 했으나 Time Limit Exceeded

2중 for문을 사용해 브루트포스 방법으로 모든 경우의 수를 돌려보려 했으나 시간복잡도가 O(n^2)여서 Time Limit에 걸린 것 같음

이중 for문을 사용하지 않는 방식을 고려해보자

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # small이 무조건 가장 작은 값이 아님 -> 계산을 한 값을 넣어야 할 것 같음
        small = prices[0]
        profit = []
        minIndex = 0
        for i in range(len(prices)):
            if prices[i]<small:
                small = prices[i]
                minIndex = prices.index(small)
            for j in range(minIndex, len(prices)):
                profit.append(prices[j] - small)
        return max(profit)

 

2번 시도 -> 이중 for문을 사용하지 않기 위해 하나의 for문 안에서 profit을 계산해서 넣는 방식으로 변경

통과!

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