[코딩인터뷰] 배열 - 주식을 사고팔기 가장 좋은 시점 문제풀이

문제

한번의 거래로 낼 수 있는 최대 이익을 산출하라.

 

입력 : [7, 1, 5, 3, 6, 4]
출력 : 5

 

위 예제에서는 1일대 구매하여 6일 경우 판매하는 것이 최대 이익 5를 얻을 수 있다. 

 

 

 

나의 코드

1) 첫번째 코드

list = [7, 1, 5, 3, 6, 4]

min_value = min(list)  # 최소값 저장
min_index = list[min_value]  # 최소값 인덱스 저장

print(list[min_value])  # 최소 값의 인덱스 찾기

if min_index == len(list) - 1:
    print(0)
else:
    # 반복문 실행
    for i, v in enumerate(list):
        if i < min_index:  # 최소값 인덱스보다 왼쪽은 pop (이유: 최소값일때 사는게 이득이고, 그 이전의 최대는 의미가 없다.)
            list.pop(i)

    # pop 으로 정리된 리스트 중 최대값 얻기
    max_value = max(list)

    print(max_value - min_value)

 

나는 최소일때 구매하면 그 후 최대값을 찾아서 산출하면 된다고 생각했다. 하지만 이는 문제가 있었다. 위 문제 설명의 예제의 경우를 보았을때 [7, 1, 5, 3, 6, 4] 리스트에서 1일 때 구매하고, 7일때 팔 수는 없다. 7은 1 구매 이전의 값이기 때문이다. 위 코드를 해결하기 위해서는 우선 반복문을 활용해야한다. 반복문은 리스트의 요소를 차례대로 탐색하기 때문에 이전의 값을 찾아올 일은 없다.

 

 

2) 제출 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_value = min(prices)  # 최소값 저장
        min_index = prices.index(min_value)  # 최소값 인덱스 저장

        if min_index == len(prices) - 1:
            return 0

        # 반복문 실행
        for i, v in enumerate(prices):
        # 최소값 인덱스보다 왼쪽은 pop
        # 이유: 최소값일때 사는게 이득이고, 그 이전의 최대는 의미가 없다.
            if i < min_index: 
                prices.pop(i)

        # pop 으로 정리된 리스트 중 최대값 얻기
        max_value = max(prices)

        return max_value - min_value


solution = Solution()
print(Solution.maxProfit(solution, [2, 4, 1]))

 

우선 min_value에 리스트의 최소값을 저장했다. 그리고 최소값의 인덱스를 찾았다. 그리고 반복문을 실행하여 최소값의 이전 요소들은 모두 리스트에서 제거한다. 그 후 max값을 찾고 max - min 을 하여 결과를 추출한다. 1)번 코드의 문제점을 해결한 코드로, 최소값의 이전 요소들은 의미가 없다고 본다. 

 

 

 

 

정답코드

1) 브루트 포스로 계산

from typing import List


def maxProfix(self, prices: List[int]) -> int:
    max_price = 0

    # 해당 풀이로는 타임아웃 문제가 발생할 것
    for i, price in enumerate(prices):
        for j in range(i, len(prices)):
            # 계속 사고 팔고를 하며 최대값을 추출한다.
            max_price = max(prices[j] - price, max_price)

    return max_price

 

2) 저점과 현재 값과의 차이 계산

import sys
from typing import List


def maxProfit(self, prices: List[int]) -> int:
    profit = 0
    min_price = sys.maxsize

    # 최솟값과 최댓값을 계속 갱신
    for price in prices:
        min_price = min(min_price, price)
        profit = max(profit, price - min_price)

    return profit

출처: github.com/onlybooks/algorithm-interview

 

 

 

 

문제풀이

1번의 정답코드 풀이

 

1) 설명

    for i, price in enumerate(prices):
        for j in range(i, len(prices)):
            # 계속 사고 팔고를 하며 최대값을 추출한다.
            max_price = max(prices[j] - price, max_price)

 

코드는 우선 간단하다. 이중 반복문을 사용하여 리스트를 탐색하여 계속적으로 각 원소의 차이를 구하여 최대값을 구한다. 이 코드는 상당히 이해하기는 쉬웠지만 타임아웃 문제가 발생할 위험이 있다.

 

 

2번의 정답코드 풀이

 

1) 설명

profit = 0
min_price = sys.maxsize

sys.maxsize를 사용하여 파이썬에서 가장 큰수를 담는다. 이렇게 담은 이유는 다음 코드에서 최소값 비교를 할때 어떠한 수가 오더라도 최소값(현재의 비교 값)이 저장된다.

 

 

2) 설명

# 최솟값과 최댓값을 계속 갱신
for price in prices:
    min_price = min(min_price, price)
    profit = max(profit, price - min_price)

 

리스트 pirces를 탐색하면서 계속해서 최솟값을 저장한다. 그리고 현재의 원소 - 저장된 최솟값을 계산하여 최대값을 갱신한다.