[1스4코2파] #152. LeetCode pattern 121. Best Time to Buy and Sell Stock

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (152일차)
[4코1파] 2023.01.13~ (143일차)
[1스4코1파] 2023.04.12~ (54일차)
[1스4코2파] 2023.05.03 ~ (33일차)

Today :

2023.06.03 [152일차]
LeetCode Patterns
121. Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

121. Best Time to Buy and Sell Stock

문제 설명

주식(Stock) 가격이 원소로 있는 prices 의 배열이 주어지는데, 해당 배열은 시간의 순서대로 주식의 가격이 담겨져있음
prices=[7,1,5,3,6,4]
첫날 7, 둘째날 1, 셋째날 5 . . .

이 prices 배열에서 사고 팔았을 때 가장 많은 이득을 return 해주면 됨

위 배열에서는 둘째날 1에 사서 다섯째날 6에 팔면 '5'의 이득을 얻게되고

prcies = [7,6,4,3,1]

해당 prices 배열에서는 언제 사도 이득을 볼 수 없기 때문에 이득은 0이다.

문제 풀이 방법

일단 가장 basic으로 생각할 수 있는 건 prices 를 하나하나 돌면서 다른 price 값과 빼고 그 값의 max를 비교하면 되는데, 그러면 O(N^2)이 나온다.
고로 효율적이 코드가 아니란 말씀..

O(N)으로 풀려고 한다면?
먼저 min_price에 양의 무한대, max_price에 0을 할당한 후 prices의 배열의 루프를 돌면서 나오는 원소 price를 min_price에 할당된 값과 비교하여 그 둘의 최솟값을 재할당하고
max_price에 할당된 값을, min_price와 max_price와 비교하여 최대값으로 재할당한다.

한번 쓱 도니까 시간복잡도도 O(n)이고, 마지막 max_price를 돌면 해당 주식 가격 배열에서 사고파는 행위를 했을 경우에 최대 이익이 나오게 된다.

내 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        minPrice, maxBenefit = float('inf'), 0
        for price in prices:
            minPrice = min(price, minPrice)
            maxBenefit = max(maxBenefit, price-minPrice)
        
        return maxBenefit

증빙

여담

어디서 많이 봤다 했더니 프로그래머스 주식가격 이었던 것