정답)
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 0번째 가격을 저장
buy = prices[0]
profit = 0
for i in range(1, len(prices)):
# 만약 다른 가격이 더 비싸다면 현재 수익과 비교 후
# 현재 수익보다 더 크다면 profit을 업데이트
if prices[i] > buy:
profit = max(prices[i] - buy, profit)
# 만약 다른 가격이 더 싸다면 사는 가격을 업데이트
else:
buy = prices[i]
return profit문제)
i번째 날의 주식 가격을 알려주는 배열 prices가 주어집니다.
당신은 하루를 정해 주식은 산 이후 미래에 팔아 최대 수익을 얻고 싶어합니다.
최대 수익을 구해서 리턴하시오. (수익을 얻을 수 없다면 0을 리턴하시오)
예시 1)
prices = [7, 1, 5, 3, 6, 4]
output = 5
예시 2)
prices = [7, 6, 4, 3, 1,]
output = 0
제한)
1 <= prices의 길이 <= 100000
0 <= prices[i] <= 10000
풀이)
코스피 지수가 계속해서 올라가던데 여러분들의 주식들은 안녕하십니까? 하시는 일 모두 잘 되셨으면 좋겠습니다.
기본원리)
배열의 가장 첫번째 가격을 변수에 저장합니다.
다른 날짜들과 비교후,
지정해둔 가격보다 비싸다면 현재 예상 수익과 비교 후 수익이 더 나는 쪽으로 저장합니다.
지정해둔 가격보다 싸다면 그 가격을 원래 저장해 두었던 변수에 새로 저장해줍니다.
모든 가격들을 비교한 후 마지막으로 저장된 수익을 리턴합니다.
초기세팅)
제한에서 prices의 길이가 적어도 1이라고 했으니 prices에는 적어도 하나의 원소가 존재합니다.
그러므로 0번째 날의 가격을 buy 변수에 저장하고
현재 수익은 없으므로 0을 profit 변수에 저장해줍니다.
def maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0i번째 날의 가격이 더 크다면)
이미 0번째 가격은 추가해줬으므로 1번째부터 가격을 비교합니다.
만약 i번째 가격이 현재 buy에 있는 가격보다 비싸다면 수익이 존재한다는 뜻입니다.
그러므로 buy 가격과 차이가 얼마나 나든지 일단은 수익을 계산해줍니다.
그리고 계산한 수익이 profit의 수익보다 크다면 현재까진 방금 계산한 수익이 최대 수익이죠?
계산한 수익이 현재 profit 보다 작다면 profit이 최대 수익입니다.
그러므로 max 함수를 사용해 방금 계산한 수익과 원래 profit을 비교해 더 큰 값을 profit에 저장해줍니다.
이렇게 원래 최대수익 (즉, profit) 이 이미 변수에 저장되어 있기 때문에
새로운 수익 (즉, prices[i] -buy)를 계속해서 발견될 때마다 구해도 되는 것입니다.
def maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0
for i in range(1, len(prices)):
if prices[i] > buy:
profit = max(prices[i] - buy, profit)i번째 가격이 buy보다 작다면?)
만약 buy보다 작은, 그러니까 현재까지 가장 작은 가격을 발견하면 어떻게 해야될까요?
가격이 더 작다는건 당연히 더 많은 수익을 의미할 수도 있기 때문에 새롭게 buy 변수에 저장해줍니다.
이렇게 새롭게 업데이트된 buy 가격으로 다른 날짜들과 비교해 최대 수익을 찾을 수도 있겠죠.
그렇게 prices를 전부 선형했다면 profit을 리턴하며 끝냅니다.
def maxProfit(self, prices: List[int]) -> int:
buy = prices[0]
profit = 0
for i in range(1, len(prices)):
if prices[i] > buy:
profit = max(prices[i] - buy, profit)
else:
buy = prices[i]
return profit디버깅)
prices = [7, 1, 5, 3, 6, 4]
buy = 7
profit = 0
(i = 1)
buy = 1
(i = 2)
profit = max(4, 0) = 4
...
(i = 5)
profit = max(5, 3) = 5
return 5
드디어 드디어 recursion이 끝났습니다! recursion이 끝나니 푸는 것도 설명하는 것도 쉬워지는군요 흑흑. 그림 한 장 안그리고 설명이 가능해서 너무 행복합니다. 참고로 전 top interview problems의 easy 단계 문제들을 전부 풀었습니다. 꾸준히 하니까 되긴 되더라구요... 뿌듯한 날입니다.
오늘도 풀이과정에 질문이나 잘못된 부분 있다면 알려주시면 감사하겠습니다 :)
'[LeetCode] > [Easy]' 카테고리의 다른 글
| [Top Interview Questions] 136. Single Number (1) | 2023.06.03 |
|---|---|
| [Top Interview Questions] 125. Valid Palindrome (0) | 2023.06.02 |
| [Top Interview Questions] 118. Pascal's Triangle (0) | 2023.05.31 |
| [Top Interview Questions] 108. Convert Sorted Array to Binary Search Tree (0) | 2023.05.30 |
| [Top Interview Questions] 104. Maximum Depth of Binary Tree (0) | 2023.05.20 |
