[Python] 1859. 백만장자 프로젝트

구현 코드 

# 매도
def sell(benefit, today, buy):
    # 산거 다 팔때까지 반복
    while buy:
        # 오늘 포인트에서 샀던거 차이 만큼 더해주기
        benefit += (today - buy.pop())
    return benefit


t = int(input())

for idx in range(1, t+1):
    n = int(input())
    # pop 사용할거기 때문에 받아온 매매가들을 뒤집어 준다.
    deal = list(map(int, input().split()))[::-1]

    buy = []        # 매수한 리스트
    benefit = 0     # 이익

    max_point = max(deal)   # 최고 주가

    while deal:
        today = deal.pop()  # 오늘 주가

        # 오늘 매매가가 최고 주가 보다 작다면 매수
        if today < max_point:
            buy.append(today)

        # 오늘 매매가가 최고 주가라면
        else:
            benefit = sell(benefit, today, buy) # 매도
            if deal:  # 다시 최고 주가 구하기
                max_point = max(deal)

    print('#{} {}'.format(idx, benefit))

 

 

그리디 코드

# 거꾸로 간다. 과거로 이동하면서 현재보다 더 높은 지점이 있다면 저장했다가 최고 높은 지점과 이동한 지점의 차익을 더한다.

t = int(input())

for idx in range(1, t+1):
    n = int(input())
    deal = list(map(int, input().split()))

    benefit = 0     # 이익
    max_point = deal.pop()  # 최고 주가

    while deal:
        today = deal.pop()  # 오늘 주가

        # 오늘 주가가 미래의 최고 주가 보다 작다면 차익 더하기
        if today < max_point:
            benefit += (max_point - today)

        # 오늘 주가가 최고 주가보다 크면 바꿔주기
        else:
            max_point = today


    print('#{} {}'.format(idx, benefit))