12. Best Time to Buy and Sell Stock

🎯 leetcode - 121. Best Time to Buy and Sell Stock

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 12번 문제

📌 날짜

2020.01.24

📌 시도 횟수

5 try + / FAILED

💡 문제 해결 방법

1. 브루트 포스 방법을 이용해 2중 for문을 이용하는 방법
- 서로 다른 2개를 뽑을 수 있는 모든 가능한 경우를 고려한다.

2. O(n)으로 풀 수 있는 방법이 무엇이 있을 지 생각했다.
- 일단 입력 list의 길이가 2보다 작으면 return 0한다.
- for문을 돌 때마다 조사 범위를 조정해가면서 profit을 갱신하는 방법은 없을까 생각했다.

😥 오류 코드 (통과 안되는 코드임)

# 오류난 코드 / 나의 시도 코드
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        index_sub, profit = 0, 0
        if len(prices) < 2:
            return 0

        for i in range(0, len(prices)):
            mx = prices.index(max(prices[: i + 1]))
            mn = prices.index(min(prices[: i + 1]))
            if mx - mn >= 0:
                if profit < prices[mx] - prices[mn]:
                    profit = prices[mx] - prices[mn]
                index_sub = mx - mn
            else:
                prices[:] = prices[mx + 1 :]
                
        if index_sub < 0:
            return 0
        return profit

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

1번 방법)
- 2중 for문을 이용하여 브루트 포스로 계산하려고 했으나 타임 아웃이 발생했다.

2번 방법)
- 일단 조사 범위를 어떻게 늘려가야 할 지 해답을 찾지 못했다.
- 내가 시도한 방법은 만약 특정 범위에서 max, min을 찾았지만 max의 index가
min의 index보다 앞에 있는 경우 max를 그냥 잘라버리는 형식으로 범위를 조정하면
어떨까 생각했는데...
- 말도 안되는 방법이었다^^... 당연히 계속해서 에러가 난다.

---

😉 다른 풀이

📌 하나. 최저점과 최댓값 profit을 계속 갱신하기

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

💡 문제 해결 방법

1. 초기 profit과 min_price를 각각 0, sys.maxsize로 초기화한다.
→ 왜냐하면 profit은 최소 0 이상이고, min_price(최저점)은 더 작은 값으로 
갱신되어야 하기 때문에 가능한 값들 중 최대로 지정해 초기화한다.
2. 맨 앞의 값부터 접근하면서 최저점을 갱신한다.
3. 최저점을 갱신할 때마다 이전에 구한 profit과 (현재값 - 최저점)을 비교하여
더 큰 값을 profit으로 지정한다.

💡 새롭게 알게 된 점

- 이렇게 한 개의 for문을 가지고 현재 값에 차례대로 접근하면서 동시에 min_price를
계속 갱신하는 방법을 통해 모든 가능한 경우를 고려할 수 있음을 알게 되었다.
- 앞으로 이렇게 O(n^2)을 O(n)으로 풀이할 수 있는 다양한 아이디어를 떠올려봐야겠다!