[Code Tree][Python] Greedy / 자동차 단일 거래 이익 최대화하기 2

Overview

• 체감 난이도: ★★☆☆☆
• 문제 유형: 그리디 
• 풀이 상태: 답안참고 / 스스로 해결
• 추후: 다시 풀어보기 / 간단 복습 / 완벽 이해 

---

[문제]

https://www.codetree.ai/missions/8/problems/max-profit-of-single-car-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

[코드]

💥 처음 푼 코드(실패한 코드)

틀린 이유

: tmp 리스트를 가격 기준으로 정렬한 후 첫 번째 원소를 buy 시점으로 선택하고 있기 때문입니다. tmp[0]의 idx와 buy를 기준으로 잡으면, 그 시점 이후에 발생하는 모든 가격과 비교하게 됩니다. 하지만 이 과정에서 매수와 매도의 순서가 시간적으로 올바르지 않을 가능성이 생깁니다.

n = int(input())
arr = list(map(int, input().split()))

tmp = []
for idx, price in enumerate(arr):
    tmp.append([idx, price])

tmp.sort(key=lambda x: x[1])

idx, buy, mx = tmp[0][0], tmp[0][1], 0
for i in range(idx, len(tmp)):
    if arr[i] - buy > mx:
        mx = arr[i] - buy

print(mx)

 

정답 코드

n = int(input())
arr = list(map(int, input().split()))

# 초기화: 첫 해의 가격을 최솟값으로 설정
min_price = arr[0]
max_profit = 0

# 두 번째 해부터 마지막 해까지 반복
for i in range(1, n):
    # 현재 가격에서 최소 가격을 뺀 값이 최대 이익보다 크면 갱신
    max_profit = max(max_profit, arr[i] - min_price)
    # 현재 가격이 최소 가격보다 작으면 최소 가격을 갱신
    min_price = min(min_price, arr[i])

print(max_profit)