주식을 사고팔기 가장 좋은 시점 p.195
문제 링크
문제 설명
- 한 번의 거래로 낼 수 있는 최대 이익을 산출
- 저점에 사서 고점에 팔아 최대 이익을 찾는 문제
입력
[7, 1, 5, 3, 6, 4]
출력
5
1일 때 사서 6일 때 팔면 5의 이익을 얻는다.풀이 전략
- 브루트 포스로 계산
- 타임아웃으로 풀리지 않는다.
- 저점과 현재 값과의 차이 계산
- 그래프 형태로 그리면 어떻게 풀어야 할지 직관이 생김
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0 # 1. 최대 이익을 저장할 변수 초기화
min_price = sys.maxsize # 2. 최소 주식 가격을 큰 값으로 초기화
for price in prices: # 3. 주식 가격 리스트를 순회
min_price = min(min_price, price) # 4. 현재 가격과 기록된 최소 가격 중 더 작은 값 선택
profit = max(profit, price - min_price) # 5. 현재 이익과 기존 최대 이익 비교 후 최대값으로 업데이트
return profit # 6. 최대 이익 반환
코드 분석
- 변수 초기화:
profit = 0: 최대 이익을 저장하는 변수입니다. 이 변수는 최종적으로 반환됩니다.min_price = sys.maxsize: 최소 가격을 저장하는 변수로, 초기값으로 매우 큰 값을 설정하여 주식 가격 중에서 가장 낮은 값을 찾아 저장할 수 있도록 합니다.
- 반복문을 통한 가격 탐색:
for price in prices:는 주어진prices리스트에서 각 가격을 순회합니다.min_price = min(min_price, price): 현재price와 이전에 저장된min_price중 작은 값을min_price에 저장합니다. 이를 통해, 주식 가격을 계속 순회하면서 가장 낮은 가격을 업데이트합니다. 이min_price는 주식을 구입할 수 있는 최적의 시점으로 간주됩니다.profit = max(profit, price - min_price): 현재 가격(price)과min_price의 차이를 계산하여, 지금까지 계산된 최대 이익(profit)과 비교 후 더 큰 값으로 업데이트합니다. 즉, 현재 가격에서 가장 저렴하게 구입할 수 있는 시점(min_price)을 뺀 값이 최대 이익이 됩니다.
- 최대 이익 반환:
- 모든 주식 가격을 탐색한 후,
profit에는 최대 이익이 저장되어 있으며, 이를 반환합니다.
- 모든 주식 가격을 탐색한 후,
예시
prices = [7, 1, 5, 3, 6, 4]일 때:
- 첫 번째 순회 (
price = 7):min_price가 7로 설정됩니다. - 두 번째 순회 (
price = 1):min_price가 1로 업데이트됩니다. - 세 번째 순회 (
price = 5):profit는5 - 1 = 4로 업데이트됩니다. - 네 번째 순회 (
price = 3):profit는 여전히 4입니다. - 다섯 번째 순회 (
price = 6):profit는6 - 1 = 5로 업데이트됩니다. - 여섯 번째 순회 (
price = 4):profit는 여전히 5입니다.
최종적으로 최대 이익은 5가 됩니다.
sys.maxsize
- 정수형의 최대값 (sys.maxsize)
- sys.maxsize는 정수형(interger) 자료형의 가장 큰 양수값, 즉 최대값을 뜻합니다.
- 반대로 sys.minsize 는 없다!
- min_num = -sys.maxsize - 1
class Solution:
def maxProfit(self, prices: List[int]) -> int:
profit = 0
min_price = sys.maxsize
for price in prices:
# print('[before] min_price='+str(min_price)+' / price='+str(price)+' / profit='+str(profit))
min_price = min(min_price, price)
profit = max(profit, price - min_price)
# print('[after] min_price='+str(min_price)+' / price='+str(price)+' / profit='+str(profit))
# print('---------')
# print('return profit='+str(profit))
return profit
# 출력
[before] min_price=9223372036854775807 / price=7 / profit=0
[after] min_price=7 / price=7 / profit=0
---------
[before] min_price=7 / price=1 / profit=0
[after] min_price=1 / price=1 / profit=0
---------
[before] min_price=1 / price=5 / profit=0
[after] min_price=1 / price=5 / profit=4
---------
[before] min_price=1 / price=3 / profit=4
[after] min_price=1 / price=3 / profit=4
---------
[before] min_price=1 / price=6 / profit=4
[after] min_price=1 / price=6 / profit=5
---------
[before] min_price=1 / price=4 / profit=5
[after] min_price=1 / price=4 / profit=5
---------
return profit=5
- prices = [7,1,5,3,6,4] 입력되어 연산을 수행한다.
- for문을 통해 prices 7부터 4까지 돌기 시작한다
- 돌면서 최저값을 찾아 기억한다
- 그리고 최대 이익 값을 찾아 기억한다.
- 반복문이 완료되면 저장된 최대 이익 값을 출력한다.