Best Time to Buy and Sell Stock

가격[i]이 i번째 날의 특정 주식 가격인 배열 가격이 제공됩니다. 특정 주식을 구매할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택하여 수익을 극대화하려고 합니다. 이 거래에서 얻을 수 있는 최대 이익을 반환합니다. 이익을 얻을 수 없으면 0을 반환합니다.

입출력 예제

Example 1:

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

접근 방향

마진을 얻기 위해서는 배열의 앞 쪽 요소가 뒤 쪽 요소보다 작아야합니다. 따라서 뒤에서부터 앞으로 가는 인덱스 포인터 하나와 앞에서 뒤로 가는 인덱스 포인터의 요소를 서로 비교하여 뒤에 있는 요소가 앞에 있는 요소보다 클 경우 그 차이를 계산하여 가장 큰 차이를 변수에 저장합니다.

나의 풀이

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        start = 0
        end = -1
        margin = 0
        tot_days = len(prices)
        # end 포인터가 맨 앞으로 오기 전까지 반복
        while end + tot_days > 0:
            # 두 포인터가 가르키는 곳이 동일하다면 end를 앞으로 진행, start를 0으로 되돌리기
            if tot_days + end == start:
                start = 0
                end -= 1
                continue

            # end 포인터 요소가 prices 포인터 요소보다 클 경우
            if prices[end] > prices[start]:
                # 최댓값 갱신
                if margin < (prices[end] - prices[start]):
                    margin = prices[end] - prices[start]
            # start 1 증가 (오른쪽으로 포인터 이동)
            start += 1

        return margin

뒤에서 시작하는 end 포인터와 앞에서 뒤로 진행하는 start 포인트가 존재하며 만약 두 포인터가 가리키는 요소의 값이 일치할 경우, 즉 len(prices) 값과 end 값을 더하였을 때 start와 동일할 경우 start 포인터를 다시 0으로 되돌리고 end 포인터는 뒤에서 앞으로 진행시킵니다. 이러한 진행 과정을 거치면서 만약 prices[end]가 prices[start]보다 클 경우 두 차이를 계산한 뒤 margin 값에 저장하여 최댓값을 갱신합니다. 하지만 이 코드는 시간 초과 테스트케이스를 통과하지 못하였습니다. 이 코드의 시간 복잡도는 O(n^2)이기 때문입니다.

정답 풀이

class Solution:
  def maxProfit(self, prices):
    left = 0
    right = 1
    max_profit = 0
    while right < len(prices):
      currentProfit = prices[right] - prices[left]
      if prices[left] < prices[right]:
        max_profit = max(currentProfit, max_profit)
      else:
        left = right
      right += 1
    return max_profit

위 코드는 left와 right 두 포인터를 사용해서 왼쪽에서 오른쪽으로 스캔하며 이동하고 right 포인터는 left보다 항상 오른쪽에 위치하게 됩니다. 만약 left 포인터의 요소가 right 포인터의 요소보다 크다면 left 포인터에 right 포인터를 대입합니다. 기존 내가 작성한 코드는 반복적으로 모든 조합을 계산하지만 위 코드는 배열을 한 번만 스캔하여 O(n)의 시간 복잡도를 가지기 때문에 더 효율적입니다.

7 1 5 3 6 4
- -           # left 포인터 요소 > right 포인터 요소이므로 left에 right 대입 후 right 증가
7 1 5 3 6 4
  - -         # left 포인터 요소 < right 포인터 요소이므로 max_profit 4 업데이트 후 right 증가
7 1 5 3 6 4
  -   -       # left 포인터 요소 < right 포인터 요소이지만 max_profit 4가 더 크므로 유지, right 증가
7 1 5 3 6 5
  -     -     # left 포인터 요소 < right 포인터 요소이므로 max_profit 5 갱신 후 right 증가
7 1 5 3 6 5
  -       -   # left 포인터 요소 < right 포인터 요소이지만 max_profit 5가 더 크므로 유지, right 증가
              # 증가된 right가 while문 조건에 포함되지 않으므로 break
              # max_profit 반환