[LeetCode] 121. Best_Time_to_Buy_and_Sell_Stock (Easy) 2023/5/3

문제 제목	정답률	난이도
121. Best-Time-to-Buy-and-Sell-Stock	54.3%	Easy

Best Time to Buy and Sell Stock - LeetCode

 

문제요약

주식 거래를 통해 이익의 최댓값을 산출해라

조건 1) 주식을 매수한 날과 매매한 날은 서로 달라야 한다

조건 2) 0 이상의 값을 가지는 가격의 배열이 주어진다

조건 3) 당연한 말이지만 매매일자는 매수일 이후이다

 

 

생각했던 풀이 1 (시간초과) : 현재 인덱스를 매수(buy)한 날로 생각

최대 이익 배열을 산출하여 해당 배열의 최댓값을 반환

최대 이익 배열 : 현재 인덱스를 기준으로, 오른쪽 부분에서 최대 이익을 산출하는 값에서 현재 값을 뺀 결과를 저장. 현재 시점의 최대 이익을 저장하는 배열

생각했던 풀이 2 : 현재 인덱스를 매매(sell)한 날로 생각

현재 시점에서 최저 매수날을 구해 최대 이익을 업데이트

 

 

풀이 1 (시간초과)

현재 인덱스를 매수(buy)한 날로 생각

 

Step1. 배열이 주어지면 매도가 최대날을 구해 뺄셈을 한 뒤 profit 배열에 추가 -> max(), 슬라이싱 이용

 

Step2. profit 배열의 최댓값 반환 -> max() 함수 이용

 

 

구현

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit=[]
        # Step 1
        for buy_day in range(0, len(prices)-1):
            profit.append(max(prices[buy_day+1:])-prices[buy_day])
        profit.append(0)
        # Step 2
        return max(profit)

풀이 1에서 시간 초과가 난 이유는 max 함수가 배열을 계속 탐색하면서 시간복잡도가 $O(n^{2})$이 되었기 때문이라고 판단한다. 따라서 max 함수의 시간 복잡도를 줄이려는 다른 생각을 해 보았다.

 

 

풀이 2 (1070ms)

현재 인덱스를 매매(sell)한 날로 생각

 

Step1. 현재 인덱스를 기준으로 매수 최솟값과 이익의 최댓값을 계속 업데이트

 

 

구현 (1057ms)

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price=prices[0]
        max_profit=0
        # Step 1
        for buy_day in range(1, len(prices)):
            min_price=min(min_price, prices[buy_day])
            max_profit=max(max_profit, prices[buy_day]-min_price)
        return max_profit

 

+예외처리 1(909ms)

최댓값이 최솟값 오른쪽에 있을 경우 해당 값을 바로 반환한다. -> max(), min(), list.index(value) 함수 이용

 

예외처리 코드 그림

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
    # 예외처리 코드 추가
        max_val=max(prices)
        min_val=min(prices)
        if (len(prices)-1-list(reversed(prices)).index(max_val))>prices.index(min_val):
            return max_val-min_val
            
        min_price=prices[0]
        max_profit=0
        for buy_day in range(1, len(prices)):
            min_price=min(min_price, prices[buy_day])
            max_profit=max(max_profit, prices[buy_day]-min_price)
        return max_profit

 

리스트에 해당 값이 있는지 확인하는 함수	list.index(value)
중복되는 원소들의 인덱스 모두 찾는 함수	numpy_array=numpy.array(list) numpy.where(numpy_array==값)[0]