leetcode 121. Best Time to Buy and Sell Stock 리트코드 121. 주식을 사고팔기 가장 좋은 시점 문제 풀이

<파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 풀이한 포스팅이다.

 

문제는 모두 리트코드에 출제된 문제들이며, 직접 풀었지만, 책에서 주는 힌트와 풀이 과정들을 참고한 경우가 많다.

이곳은  정리한 책에 나온 문제에 대한 목록과 해설을 정리한 공식 깃허브 페이지 이며, 

다음 포스팅은 내가 푼 <파이썬 알고리즘 인터뷰> 문제 풀이 목록을 정리해 놓았다.

 

문제

주식을 사고팔기 가장 좋은 시점 

 

입력: 정수로 된 리스트

출력: 정수

 

문제 요약: 리스트 안의 숫자 2개를 골라서 그 차가 가장 큰 값을 출력 (순서 있음)

유의 사항: 유의사항을 보면 제시된 리스트의 길이와 숫자의 크기가 매우 크다. 효율성을 고려해야 한다.

생각 과정

기본적으로 가장 큰 수에서 가장 작은 수를 빼면 차이가 가장 크다.

그러나 리스트의 순서에 의미가 있기 때문에 그냥 정렬을 하면 안된다.

이럴 때는 for 반복문을 돌리면서, 새로 들어온 원소가 더 작으면, 최소값을 바꿔주면 된다.

차이는 최소값 보다 더 뒤에 있는 숫자에 최소값을 빼줄 때 생기는 것으로, 그것 또한 새로 차이가 생길 때 기존의 차이와 비교해 더 크면, 차이 값을 바꿔준다.

풀이

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = prices[0]
        for i in prices: 
            if i < min_price: 
                min_price = i
            elif i - min_price > profit: 
                profit = i - min_price
        return profit