코딩테스트 풀이/리트코드

[LeetCode] Best Time to Buy and Sell Stock 문제 풀이 (Array 이용, Python)

개발하는 감자입니다 2023. 12. 22. 00:30
728x90

안녕하세요! 개발감자 박그냥입니다🥔

페이스북 개발자가 추천한 알고리즘 문제에서 가장 쉬운 2번 문제에 해당하는 <121. Best Time to Buy and Sell Stock> 문제 풀이입니다. 언어는 파이썬으로 진행하였습니다. 파이썬 문법을 제외하고 이 문제에 대한 아이디어 위주로 이야기해볼게요. 

 

1. 문제 설명

1) 문제 이름
: Best Time to Buy and Sell Stock

2) 문제 난이도
: Easy

3) 문제 해석
: 당신에게 prices 배열이 주어집니다. 여기서 prices[i]는 i번째 날의 특정 주식 가격입니다.
여러분은 한 날에 주식을 사고 미래의 다른 날에 그 주식을 팔아서 이익을 극대화하고 싶습니다.
이 거래로부터 얻을 수 있는 최대 이익을 반환하세요. 만약 어떤 이익도 얻을 수 없다면 0을 반환하세요.

 

  • 개발감자의 문제 해석 : 주식의 가격이 담긴 리스트를 줄 건데 가장 이익이 클 때가 언제니? 그 값을 구해봐~

 

2. 아이디어

저는 이번에도 무조건 반복문을 한 번 쓸 것이다라고 생각했습니다.

아무래도 중첩 반복문을 사용하면 시간 복잡도가 올라가기 때문이에요. 주식 리스트를 돌면서 가장 작은 주식 가격과 가장 큰 이익을 동시에 구합니다. 현재 가장 작은 주식보다 지금 보고 있는 주식 가격이 작으면 가장 작은 주식의 가격을 지금 주식 가격으로 업데이트하고 아니라면, 원래 있던 가장 작은 주식 가격과의 차이 즉, 이익을 구해 원해 있던 이익이랑 비교해서 더 크면 저장하는 것입니다. 신경써야 하는 건 무조건 파는 주식의 항목의 인덱스가 사는 주식의 인덱스보다 커야 한다는 것이었습니다. 무턱대로 가장 큰 값을 구하면 안되겠죠?

 

정리하자면

1) 리스트를 처음부터 끝까지 한 번 훑는다
2) 가장 작은 주식 가격보다 지금 주식 가격이 작으면 가장 작은 주식 가격을 업데이트 합니다.
3) 이익이 전에 있던 이익보다 크면 업데이트 한다.

 

 

3. 풀이 설명

class Solution(object):
    def maxProfit(self, prices):
        if not prices or len(prices) < 2:
            return 0

        min_price = prices[0]
        max_profit = 0

        for price in prices[1:]:
            if price < min_price:
                min_price = price
            else:
                max_profit = max(max_profit, price - min_price)

        return max_profit

 

 

위의 아이디어를 어떻게 실현했는지를 보면서 이해하시면 더 이해가 잘 될 겁니다.

1) 리스트를 처음부터 끝까지 한 번 훑는다
2) 하나의 주식을 기준으로 리스트를 두개로 나누고, 이익을 구한다.
3) 이익이 전에 있던 이익보다 크면 업데이트 한다.

 

1) 리스트를 처음부터 끝까지 한 번 훑는다

if not prices or len(prices) < 2:
            return 0

        min_price = prices[0]
        max_profit = 0

        for price in prices[1:]:

 

주식의 리스트나 리스트의 크기가 2보다 작으면 0을 리턴하도록 했습니다. 주식을 파고 살 수 없기 때문이죠!

일단 시작할 때, 가장 작은 주식의 가격을 주식 리스트의 첫 번째에 있는 주식으로 설정합니다.

가장 큰 이익도 0으로 설정하고 시작합니다!

 

이제 주식 리스트를 처음부터 끝까지 훑어야겠죠? 첫 번째 주식을 제외한 리스트를 돕니다. 왜냐하면 이미 맨 앞의 주식은 가장 작은 주식 가격에 저장해뒀기 때문이에요!

2) 가장 작은 주식 가격보다 지금 주식 가격이 작으면 가장 작은 주식 가격을 업데이트 합니다.

 if price < min_price:
	min_price = price

 

 

3) 이익이 전에 있던 이익보다 크면 업데이트 한다.

else:
	max_profit = max(max_profit, price - min_price)

 

2번의 경우가 아니라면 이 경우로 넘어갑니다. 현재 주식 가격과 저장하고 있는 가장 작은 주식의 가격의 차이를 구합니다.

저장하고 있는 이익과 비교하고 가장 큰 것을 이익(max_profit)에 저장합니다.

성공화면 ><

이렇게 문제 풀이를 완료해보았습니다. 문제를 푸는 분들에게 도움이 되었으면 좋겠습니다.

그럼 더 알찬 포스팅으로 돌아올게요. 개발감자였습니다.

 

 

728x90
반응형