[알고리즘 일기] 39. 삼송전자 주식 분석

문제 39. (2021-06-08)

삼송전자 주식 분석

태호는 주식 분석이 취미입니다.

요즘 제일 핫한 종목은 삼송전자인데요. 삼송전자의 주식을 딱 한 번 사고 팔았다면 최대 얼마의 수익이 가능했을지 궁금합니다. 그것을 계산해 주는 O(n)

O(n) 함수 max_profit을 작성하세요.

max_profit은 파라미터로 일별 주식 가격이 들어 있는 리스트 stock_prices를 받고 최대 수익을 리턴합니다. 주식은 딱 한 번만 사고 한 번만 팝니다. 그리고 사는 당일에 팔 수는 없습니다.

하나의 예시로, 지난 6일간 삼송전자의 주식 가격이 이렇다고 가정합니다.

max_profit([7, 1, 5, 3, 6, 4])

이 기간 동안 낼 수 있는 최대 수익은 둘째 날 1에 사서 다섯째 날 6에 팔면 총 5의 수익이 생깁니다.

❧ 테스트 셋

def max_profit(stock_list):
    # Code

# Test
print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
print(max_profit([11, 13, 9, 13, 20, 14, 19, 12, 19, 13]))
print(max_profit([12, 4, 11, 18, 17, 19, 1, 19, 14, 13, 7, 15, 10, 1, 3, 6]))

❧ 출력 예시

5 
-1 
11 
18

---

❧ 정답

def max_profit(stock_list):
    profit = stock_list[1] - stock_list[0]
    for i in range(len(stock_list)-2):
        # i 인덱스 뒤에 있는 값들을 내림차순으로 정렬한 뒤 최댓값 추출
        sorting_list = sorted(stock_list[i + 1 : len(stock_list)-1], reverse = True)
        # max로 수익 최대값 갱신
        profit = max(profit, sorting_list[0] - stock_list[i])
    return profit

print(max_profit([7, 1, 5, 3, 6, 4]))
print(max_profit([7, 6, 4, 3, 1]))
print(max_profit([11, 13, 9, 13, 20, 14, 19, 12, 19, 13]))
print(max_profit([12, 4, 11, 18, 17, 19, 1, 19, 14, 13, 7, 15, 10, 1, 3, 6]))

1️⃣ 시간 복잡도 : O(n)

2️⃣ 앞에서 부터 주식을 산 시기로 가정한다. (for 문에서의 i)

3️⃣ 뒤에 있는 리스트들을 정렬하여 주식을 산 시기부터 가장 최대값 계산