[알고리즘] 총 한 번 매수/매도 시 최대 이익

문제

주식 투자를 즐기는 홍길동은 n일 동안 어떤 회사의 주식을 다음과 같이 매매한다: 주식 한 주를 한 번만 사서 이를 다음에 한 번 팔 수 있다. 홍길동은 n일 동안 주식 매매(한번 사서 한번 팜)를 하여 얻은 이익에 대하여, 얻을 수 있는 최대 이익과 얼마나 차이가 있는지를 알고 싶어한다. 그래서 이 기간동안 얻을 수 있는 최대 이익을 계산하기로 하였다. 예를 들어, 7일 동안 주식 가격이 (30, 25, 50, 10, 20, 40)과 같을 때, 최대 이익은 네째 날 주식을 사서 마지막 날 팔면 이익이 30(=40–10)이다. n일 동안 주식 가격이 주어질 때, 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에는 n이 주어진다. n은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 주식 가격(양의 정수)이 날짜 순서대로 n개 주어진다.

출력 형식

최대 이익을 첫 번째 줄에 출력한다. 두 번째 줄에 사는 가격과 파는 가격을 각 각 출력한다. 최대이익을 얻는 경우가 여러 개인 경우, 사는 가격이 최소인 경우 하나만 출력한다. 이득이 없는 경우는, –1만 출력한다.

나의 풀이

처음에는 DP로 접근을 했다.

a = int(input())
b = list(map(int, input().split()))

b_max = b[-1]
b_min = b[0]
if 2 <= a <= 100000:
    profit = [0] * a
    for i in range(a-2, -1, -1):
        if b[i] > b_max:
            b_max = b[i]
        if b[a-i-1] < b_min:
            b_min = b[a-i-1]
        if b.index(b_max) > b.index(b_min):
            profit[i] = max(profit[i+1], b_max - b[i])

if max(profit) != 0:  # profit의 max값이 0이 아닐 경우
    print(max(profit))  # 마지막 인덱스부터 첫 번째 인덱스까지 다 돈 후에 가장 앞의 값. 즉 profit의 max값임
    print(b_max, b_min)
else:  # profit의 max값이 0인 경우. 즉 최대 이익이 0인 경우
    print(-1)  # -1 출력

그래서 이렇게 풀었다. 0이 a개만큼 들어간 리스트를 만들고 그곳에 최대값을 넣는 방식이었다. 헌데, 이렇게 할 경우 최대 이익은 출력할 수 있었으나, 문제는 사는 가격과 파는 가격을 각각 출력하지 못한다는 것이었다. 이게 조그마한 부분만 고치면 된다고 생각이 들게 되면서 다르게 생각할 수 있는 여지를 없애고 생각을 좀먹는다. 아예 처음부터 다시 시작해보자고 해서 한 게 아래와 같은 코드이다.

import sys
a = sys.stdin.readline()

b = list() # 후보 값 리스트
price = list(map(int, sys.stdin.readline().split())) # 가격 리스트

price_max = price[0]
price_max_index = 0
price_min = price[0]
price_min_index = 0

for i in range(1, len(price)):
    n = price[i]
    if price_max < n:  # n이 원래의 max값보다 클 경우에는 n을 max값으로 업데이트하고, 인덱스를 i로 업데이트함
        price_max = n
        price_max_index = i
    elif price_min > n:  # n가 원래 min값보다 작을 경우엔 리스트에 기존 값을 담고 다시 돌린다.
        b.append((price_max - price_min, price_max, price_min))
        price_min = n
        price_min_index = i
        price_max = n
        price_max_index = i

b.append((price_max- price_min, price_max, price_min))
# for문이 끝나고 난 뒤의 최대 이익(price_max - price_min)과, 최대값과 최소값을 각각 넣는다.

price_sorted = sorted(b, key=lambda n: (-n[0], n[2]))
# b를, 앞에서부터 이익이 큰 값을 넣고, 이익이 같은 경우 최소값이 낮은 것부터 넣는다.

if price_max_index <= price_min_index:  # 최대값 인덱스가 더 작을 경우. 이럴 땐 최대 이익이 없으므로 -1 출력
    print(-1)
else:
    print(price_sorted[0][1] - price_sorted[0][2])
    print(price_sorted[0][2], price_sorted[0][1])

위에 설명한 그대로이다. 이중 배열을 이용했다. 알고리즘은 너무 어렵다.. 작년부터 시작할걸 하는 후회가 살짝 든다.