LeetCode 121(Best Time to Buy and Sell Stock, Python)

1. 문제 링크

• Best Time to Buy and Sell Stock - LeetCode

Best Time to Buy and Sell Stock - LeetCode

2. 문제 설명

• 하루하루 주식 가격이 기록된 리스트를 입력받았을 때, 낼 수 있는 최대 이익을 구하는 문제. 사고 나서 팔아야 함에 유의(팔고 난 후 살 순 없음)
• 예시1) prices = [7,1,5,3,6,4]인 경우 1에 사서 6에 팔면 최대 이익 5. 이때 7에 팔고 나서 1에 살 순 없음. 
• 예시2) prices = [7,6,4,3,1]인 경우 사면 무조건 손해이므로 최대이익은 0

3. 처음 풀이

• m에 사서 M에 판다. 일단은 첫날 가격을 m과 M에 저장.
• 이후 둘째날부터 가격이 M보다 크면 둘째 날 가격에 팔아야 하므로 M을 업데이트,
• 가격이 m보다 작으면 그전까지 최대 이익을 temp에 업데이트해 두고 이 날을 다시 첫째 날처럼 생각하여 반복
• 논리는 간단한데 다른 풀이보다 오래 걸림. pop()가 O(1) 인줄 알았는데 아래 코드처럼 pop(0)을 하면 O(n)이라 오래 걸림.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        temp = 0
        m = M = prices[0] #buy m=1st day price, sell M=1st day price
        while prices:
            if prices[0]>M: #update sell price
                M = prices.pop(0)
            elif prices[0]<m: #if current price is lower than buy price
                temp = max(temp, M-m) #update max profit until now, buy m=current price, sell M=current price
                m = M = prices.pop(0)
            else:
                prices.pop(0)
        return max(temp,M-m)

 

4. 다른 풀이

• 같은 논리지만 훨씬 빠르다. 위의 코드에서는 while 문 안에 pop가 들어가서 시간복잡도가 n제곱, 아래 코드는 for문 한 번 돌아서 n

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        temp = 0
        m = M = prices[0]
        for price in  prices:
            if price>M:
                M = price
            elif price<m:
                temp = max(temp, M-m)
                m = M = price
        return max(temp,M-m)

---

• 무한대를 이용할 수 있음. 
• 무한대에 사서 이익 0이라고 해두고 시작. 
  • 현재 가격이 구매 가격보다 싸면 구매가격을 업데이트
  • 현재 가격 - 구매가격 > 현재까지 최대 이익 이면 최대 이익 업데이트

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minn ,maxx = float('inf'),0
        for price in prices:
            if price < minn:
                minn = price 
            if price - minn >maxx:
                maxx = price-minn
        return maxx

5. 배운 점

• 무한대를 나타내기 위해 float 데이터 타입의 inf를 사용할 수 있음.
• float('inf')는 양의 무한대, float('-inf')는 음의 무한대를 나타냄. 

positive_inf = float('inf')
negative_inf = float('-inf')

print(positive_inf > 10000)  		# True
print(positive_inf > negative_inf)  	# True
print(positive_inf + 10)  		# inf
print(negative_inf - 5)   		# -inf
print(positive_inf + positive_inf)  	# inf
print(negative_inf - negative_inf)  	# inf
print(positive_inf * 0) 		# nan (Not a Number)
print(negative_inf / 0) 		# -inf
print(positive_inf * positive_inf)  	# inf
print(negative_inf / positive_inf)  	# -0.0

---

• pop()은 리스트의 요소를 삭제하며 해당 요소를 반환하는 메소드
• list.pop()의 경우 리스트의 마지막 요소를 삭제하며 시간 복잡도는 O(1)
• 하지만 list.pop(0)의 경우 리스트의 첫 번째 요소를 삭제하며 시간 복잡도는 O(n)으로 다르며 리스트 길이가 길어질수록 비효율적임.