LeetCode-121 Best Time to Buy and Sell Stock 파이썬 문제 풀이

Best Time to Buy and Sell Stock - LeetCode

 

문제

매일 달라지는 주식의 값이 배열에 저장되어 있습니다. 배열의 0부터 하루 지날떄마다 다음 순서로 넘어간다고 했을 때 한번 사고, 한번 팔수 있었을 때 낼 수 있는 가장 큰 이익을 구하는 문제입니다. 즉, 항상 주식을 산날이 판날보다 먼저 위치해 있어야 합니다.

풀이

처음 작성해본 코드는 가장단순한 방법으로 배열을 순회하면서 가장 차이가 클 때를 찾는 것입니다. 배열의 순서가 날짜의 순서이기때문에 지나간 배열의 차까지는 구할 필요가 없습니다. i로 배열을 하나씩 순회하고 j로 i부터 배열의 끝까지 순회하며 i인덱스와 j인덱스를 가진 두 배열 요소의 차를 구합니다. 만약 저장되어있는 가장 작은 차보다 현재 구한 차이가 더 크다면 해당 값으로 저장합니다. 하지만 당연하게도? 이 방법은 시간 초과가 났습니다ㅎㅎ.. 테스트 시에는 문제가 없지만 입력 값이 많아질 경우에는 문제가 되었습니다.

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

 

두번째 시도했던 방법은 현재 위치해있는 배열의 요소와 지나간 배열중 가장 작은 값과의 차이를 구하는 방법입니다. 먼저 지나왔전 배열 중 가장 작은 값을 저장하기 위해서 매번 가장 작은 값으로 저장되어있는 요소와 현재 요소를 비교하여 더 작은 값을 저장해두도록 합니다. 이렇게하여 minprice에 현재 까지 지나온 요소들 중 가장 작은 값을 저장하도록 할 수 있습니다. 동시에 현재 요소값과 minprice의 차이를 계산하여 profit에 저장되어 있는 값보다 크다면 해당 차이를 profit에 저장합니다. for문을 끝까지 실행했을 경우 가장 큰 이익을 profit에 저장해두었기 떄문에 profit의 값을 반환하면 됩니다.

 

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