121. Best Time to Buy and Sell Stock

문제

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

예시

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        p = 0
        for n in reversed(range(1, len(prices))):
            min_p = min(prices[:n])
            p = max(p, prices[n] - min_p)
        return p

주어진 input 리스트에서 가장 큰 원소의 차를 구하는 문제이다. 그리고 원소(j) - 원소(i) 일 때, 항상 j > i 라는 조건이 있다. 처음에는 맨 뒤부터 하나씩 빼나가는 방법을 적용해보았지만 time limit이 발생하게 되었다.

두번째 방법으로는 모든 원소와의 차를 구한 뒤에 max를 구하는 것보다 해당 위치 이전 원소들에서 가장 작은 값과만 빼주면 된다는 생각에 min()을 사용해 최소값을 구한 후에 차를 구하는 방법을 사용했다.

다행히 통과는 했으나 굉장히 오래걸리는 결과를 볼 수 있다. 아마도 매번 min() 을 하게 되면서 연산 속도가 느려지는 것 같다고 생각된다. 그래서 다른 풀이를 참고해 보았다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        profit = 0
        min_price = 1000000000000000000
        for price in prices:
            min_price = min(min_price, price)
            profit = max(profit, price - min_price)
        return profit

매우 심플하다. 순서대로 price를 확인하면서 최소 price와 최대 profit을 매번 업데이트하게 된다.

결과

• 풀이 1

  200 / 200 test cases passed.
  Status: Accepted
  Runtime: 5992 ms
  Memory Usage: 15 MB

• 풀이 2

  200 / 200 test cases passed.
  Status: Accepted
  Runtime: 76 ms
  Memory Usage: 14.9 MB