[반복문] LeetCode 121번 문제 학습

문제를 푼 과정

 

• 처음엔 완전 탐색으로 구현해봤음
  → 모든 날짜 쌍을 비교해서 최대 이익을 구하는 방식
  → 작은 입력엔 잘 돌아가지만 큰 입력에서 느려짐
• 그래서 최적화된 알고리즘으로 개선함
  → 지금까지 본 가장 싼 가격(minPrice) 을 저장해두고
  → 현재 가격 - minPrice 로 이익을 계산해서 최대값을 업데이트함
  → 이러면 한 번의 순회로 해결 가능해서 시간복잡도 O(n)임

 

문제에 대한 설명

주어진 배열 prices는 각 날짜의 주식 가격을 의미함.
이 중 하루를 골라 주식을 사고, 그 이후 중 하루를 골라 팔아서
얻을 수 있는 최대 이익을 구하는 문제임.

조건은 단순함:

• 한 번만 사고, 한 번만 팔 수 있음
• 무조건 나중에 사는 게 아님. 산 날보다 뒤에 팔아야 함

---

문제를 풀려면 어떤 알고리즘을 써야 하는지

처음 떠오를 수 있는 건 완전 탐색(Brute-force) 방식임.

• 모든 (i, j) 쌍을 비교해서 prices[j] - prices[i] 계산함
• 시간복잡도 O(n²)라서 입력 수가 많으면 시간 초과 발생함

그래서 더 효율적인 방식인 단일 패스 + 최소값 갱신 방식을 써야 함
이건 일종의 그리디 알고리즘 + 누적 최소값 저장 전략임.

 

package main

import "fmt"

func maxProfit(prices []int) int {
	var minPrice int = prices[0]
	var maxProfit int = 0

	for i := 1; i < len(prices); i++ {
		if minPrice > prices[i] {
			minPrice = prices[i]
		} else {
			if maxProfit < prices[i] - minPrice {
				maxProfit = prices[i] - minPrice
			}
		}
	}

	return maxProfit
}

func main() {
	var price1 []int = []int{7, 1, 5, 3, 6, 4}
	var price2 []int = []int{7, 6, 4, 3, 1}

	fmt.Println(maxProfit(price1)) // Output: 5
	fmt.Println(maxProfit(price2)) // Output: 0
}