[Leetcode 아주 상세한 문제풀이] 121. Best Time to Buy and Sell Stock - 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 121번 문제 Best time to buy and sell stock 다.

우선 문제를 살펴보자.

 

리트코드 121번 문제 Best time to buy and sell stock (링크)

Best Time to Buy and Sell Stock - LeetCode

Best Time to Buy and Sell Stock - LeetCode

 

 

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 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.
 
Constraints:
1 <= prices.length <= 105
0 <= prices[i] <= 104

 

 

문제 설명

문제에 대해 간략히 살펴보면, 주식 가격이 표시된 배열이 주어진다. 이때 배열의 index는 날짜를 나타낸다. 즉, index 0은 Day1, index 1은 Day2 이런식이다. 이때 언제 사서 언제 팔아야 가장 큰 수익을 낼 수 있는지 알아내 그때의 수익을 출력하라는 것이 문제에서 요구하는 바다. 물론 실제 주식거래에서 일어나는 일들 (공매도 등)은 생각하지 말자. 삼척동자도 알 수 있듯이 가장 큰 수익을 내기 위해서는 가격이 가장 낮을 때 사서 가장 높을때 팔면 된다. 물론 오늘 산 주식을 어제 가격으로 팔 수 없다.

 

 

문제 접근법

앞서 언급했듯 이 문제에 접근하기 위해서는 '시간 흐름'에 따른 가격을 계산해야 한다는 것이다. 예제 1번에서 보는 것처럼 두번째 날 최저 가격이 1이어도 우리는 다섯번째 날 6에 팔아야지, 다시 첫째날 가격 7로 팔 수 없다는 것이다.

위 조건은 이 문제를 푸는데 굉장히 중요한데,

주어진 배열을 첫번째 index부터 탐색해나가며

1) 그 가격이 최저 가격인지

2) 그리고 그때 가격에서 최저 가격으로 구매한 주식을 팔면 얼마나 수익이 나는지

위 두개를 tracking하면 된다.

 

 

문제 풀이

코드를 한 번 살펴보자.

우선 주식 가격이 담긴 배열을 입력받을 함수를 정의해 준다 (line 1)

만약 입력받은 배열이 비어있다면 0을 리턴해준다 (line 2)

앞서 말했든 최저 가격과 최대 수익을 tracking 해줘야 하는데

우선 최저 가격은 Day 1의 주식 값 (Index = )으로 초기화를 시켜주고 (line 5)

최대 수익은 0으로 초기화를 시켜준다 (line 6)

입력된 배열 안의 숫자를 for loop를 통해 돌려주는데 (line 8)

만약 그 때 가격이 최저 가격보다 낮다면 최저 가격을 업데이트 해준다 (line 9)

만약 그 때 가격이 최저 가격보다 높다면 수익이 얼마나 났나 계산을 해야하는데

그때 가격에서 최저 가격 사이이 차이와 지금까지의 최대 수익 값을 비교해

둘 중 더 큰 값을 최대 수익 값에 업데이트 해준다 (line 12)

 

 

문제 풀이 코드

def max_profit(prices):
    if not prices:
        return 0
    
    min_price = prices[0]
    max_profit = 0
    
    for price in prices:
        if price < min_price:
            min_price = price
        else:
            max_profit = max(max_profit, price - min_price)
    
    return max_profit
 
# Example usage
input_prices = [7, 1, 5, 3, 6, 4]
result = max_profit(input_prices)
print(result)  # Output: 5
 

 

문제에 대한 접근 방식을 정확히 파악하면 굉장히 쉽게 풀 수 있는 문제였다.

이상 리트코드 121번 Best time to buy and sell stock 문제풀이였다.

 

 

관련 문제

 

리트코드 1번 문제 Two sum 문제풀이

리트코드 11번 문제 Container with most water 문제풀이

리트코드 15번 문제 3Sum 문제풀이

리트코드 33번 문제 Search in rotated sorted array 문제풀이

리트코드 53번 문제 Maximum subarray 문제풀이

리트코드 152번 문제 Maximum product subarray 문제풀이

리트코드 153번 문제 Find minimum in rotated sorted array 문제풀이

리트코드 217번 문제 Contains duplicate 문제풀이

리트코드 238번 문제 Product of array except self 문제풀이

리트코드 238번 문제 Product of array except self 문제풀이

 

 

121. Best Time to Buy and Sell Stock