LeetCode 코딩테스트 Best Time to Buy and Sell Stock – Array(2)

by

LeetCode는 소프트웨어 엔지니어링 및 코딩 인터뷰 준비를 위한 플랫폼이다. 다양한 프로그래밍 언어로 구현된 코딩 문제가 공하며 알고리즘 능력을 향상시키는데 도움을 준다.

LeetCode에 수 많은 문제 중에 시간을 절약하기 위해 New Year Gift – Curated List of Top 75 LeetCode Questions to Save Your Time 에서 각 카테고리/유형 별로 추천하는 75개 문제를 풀어본다.

이번 POST에서는 Array문제인 Best Time to Buy and Sell Stock 문제를 python으로 풀어보았다.

Leetcode 문제설명

이 문제는 주어진 주식 가격 배열에서 최대 이익을 얻기 위한 전략을 찾는 문제이다. 주어진 가격 리스트에서 하루에 주식을 한번 사서 다른 날에 팔아 얻을 수 있는 이익을 구한다.

해당 문제는 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/에서 확인할 수 있습니다.

첫번째 예제에서 최대이익을 얻는 방법은 가장 싸게 구매할 수 있는 1에 사서 6에 파는 방법으로 최대 이익은 6-1 = 5 이다.

두번째 예제에서는 어떤 날 주식을 사더라도 가격이 계속 떨어져 이익을 얻을 수 없으므로 최대이익은 0 이다.

솔루션

2중 for문으로 간단하게 구현할 수 있다. 하지만 다음 방법으로 구현하게 되면 시간 복잡성이 O(n2)이므로 큰 데이터 세트에서는 효율적이지 않을 수 있다. 제출시에도 Time Limit Exceeded 오류가 발생하였다.

class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0  # 최대 이익을 저장할 변수 초기화
        
        for i in range(len(prices)):  # 주식을 사는 날을 선택
            for j in range(i + 1, len(prices)):  # 주식을 팔 날을 선택
                profit = prices[j] - prices[i]  # 주식을 팔아서 얻는 이익 계산
                
                if profit > max_profit:  # 현재까지의 최대 이익보다 크다면 업데이트
                    max_profit = profit
        
        return max_profit  # 최종적으로 찾은 최대 이익 반환
leetcode-Best-Time-to-Buy-and-Sell-Stock

문제를 효율적으로 계산하기위해서 코드를 보완하였다. 아래 알고리즘의 시간 복잡성은 O(n)이므로 큰 입력 데이터에서도 빠르게 실행된다.

class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0  # 주어진 주식 가격이 없으면 이익은 0이다.
        
        min_price = prices[0]  # 현재까지의 최저 가격을 첫 번째 주식 가격으로 초기화
        max_profit = 0  # 최대 이익을 0으로 초기화
        
        for price in prices:
            min_price = min(min_price, price)  # 현재 주식 가격이 최소 가격보다 작으면 최소 가격을 업데이트
            max_profit = max(max_profit, price - min_price)  # 현재 주식을 팔았을 때의 이익이 최대 이익보다 크면 최대 이익을 업데이트
            
        return max_profit  # 최종적으로 찾은 최대 이익 반환
  1. 먼저, 함수는 prices 리스트가 비어있는지 확인합니다. 만약 prices가 비어 있다면, 즉 주식 가격이 주어지지 않은 경우에는 이익을 얻을 수 없으므로 0을 반환한다.
  2. 그 다음으로, min_price와 max_profit라는 두 개의 변수를 초기화한다.
  3. min_price 변수는 현재까지의 최저 가격을 저장하는 변수이다. 초기값으로 prices 리스트의 첫 번째 요소(prices[0])를 사용한다.
  4. max_profit 변수는 최대 이익을 저장하는 변수로, 초기값은 0이다.
  5. 이제 for 루프를 사용하여 prices 리스트의 각 가격(price)에 대해 반복한다.
  6. 각 반복에서, min 함수를 사용하여 현재까지의 최저 가격(min_price)과 현재 가격(price) 중 작은 값을 선택하고, min_price 변수에 저장한다. 이렇게 하면 현재까지의 최소 가격을 업데이트한다.
  7. 다음으로, 현재 가격(price)에서 최소 가격(min_price)을 뺀 값을 사용하여 현재 날짜에 주식을 팔면 얻을 수 있는 이익을 계산한다. 이 계산한 이익을 max 함수를 사용하여 현재까지의 최대 이익(max_profit)과 비교하고, 만약 계산한 이익이 현재까지의 최대 이익보다 크다면, max_profit 변수를 업데이트하여 최대 이익을 갱신한다.
  8. for 루프가 모든 주식 가격에 대해 반복하고 나면, max_profit 변수에는 최대 이익이 저장되어 있다.
  9. 마지막으로, 최대 이익(max_profit)을 반환한다.

다음글은 Contains Duplicate 문제입니다.

LeetCode 코딩테스트 Contains Duplicate – Array(3)

Leave a Comment