LeetCode 121. Best Time to Buy and Sell Stock

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.

 

해당 날짜의 특정 주식 가격을 나타내는 prices배열 이 제공됩니다 .prices[i]ith

특정 주식을 구매할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택 하여 수익을 극대화하려고 합니다 .

이 거래에서 얻을 수 있는 최대 이익을 반환합니다 . 이익을 얻을 수 없으면 를 반환하십시오 0.

 

 

 

 

풀이

최초풀이 - 리스트에서 for문을 통해 값을 순회하며 뒤의 숫자와 비교하여 차액이 가장 큰 곳을 찾았다 .

 

def maxProfit(self, prices):
    result = 0
    for i in range(len(prices)): # 각 날짜의 가격을 순회하며 현재위치에서 뒤의 인덱스의 값을 계산 후 비교
        for j in range(i+1,len(prices)):
            if prices[j]- prices[i] > result:
                result =  prices[j]- prices[i]
    return result
    시간복잡도 n^2

시간초과가 떴다  ㅎㅎ.. 브루트포스로는 안되나보다..

 

생각을해보니 가장 차액이 큰 걸 찾기위해서 그냥 for문을 돌면서 최솟값과 최대값을 갱신하며 차액을 구하면된다는걸 깨달았다. 

 

[9,1,1,1,8] 이런식으로 숫자가 배열된다면 최대값을 9 최소값을 1로 판단해서 8을 반환하겠지..?

 

그냥 최솟값만 가지고가면서 각 숫자를 계산해주기만 하면 되는 간단한 문제가 아닐까? 

 

class Solution(object):
    def maxProfit(self, prices):
        result = 0  			# 최대이익값 
        min_value = prices[0]   # 최초에 첫번째 값을 가장 작은값으로 측정 
        for i in prices:    	#for문으로 각 날자별 가격 순회
            if i < min_value:   # 가장 작은 값 비교  작다면 작은 값 갱신 
                min_value = i
            if result< i- min_value: # 가장 작은 값과 현재 인덱스의 값을 비교 
                result = i- min_value
        return result
        
 #sudo
 result = 최고이익
 min_value = 현재까지 나온 값 중 제일 적은 값
 for 당일가격  in 각 날자 별 가격리스트: 
 	if 당일가격 < min_value (제일 적은 값):
    		제일 적은 값 = 당일 가격
    if 최고이익 < 당일가격 - 제일 적은 값:
    	최고이익 = 당일가격 - 제일 적은 값
retrun 제일 적은 값

 

맞다.. 그냥 제일 작은 값을 가지고 각 리스트를 돌며 비교해주니 솔했다 굳굳

 

class Solution:
    def maxProfit(self,prices):
        left = 0 #Buy
        right = 1 #Sell
        max_profit = 0
        while right < len(prices):
            currentProfit = prices[right] - prices[left] #our current Profit
            if prices[left] < prices[right]:
                max_profit =max(currentProfit,max_profit)
            else:
                left = right
            right += 1
        return max_profit

투포인터를 이용해서 문제를 푸는 방법 각 위치를 움직이며 최대이익값을 그리디하게 찾는다.