문제 설명
홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.
- 주식 하나를 산다.
- 원하는 만큼 가지고 있는 주식을 판다.
- 아무것도 안 한다.
홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.
예를 들어, 날 수가 3일이고 주가가 10, 7, 6이라면 주가는 계속 감소하므로 최대 이익은 0이 된다. 하지만 날 별 주가가 3, 5, 9라면 첫 두 날에 주식을 하나씩 사고 마지막 날 모두 판매하면 총 이익은 10이 된다.
입력
- 첫 줄에는 테스트케이스 수
T가 주어진다. - 각 테스트케이스 별로 첫 줄에는 날의 수
N(2 \leq N \leq 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는N개의 자연수(10,000이하)가 공백으로 구분되어 순서대로 주어진다.
출력
각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 64bit 정수형으로 표현 가능하다.
풀이 방법
이 문제는 그리디 알고리즘(Greedy Algorithm) 을 활용하여 해결할 수 있다. 핵심 아이디어는 주식을 언제 사고팔아야 최대 이익을 얻을 수 있는지 결정하는 것이다.
1. 내가 처음 접근한 방법
처음에는 주가 리스트를 앞에서부터 순차적으로 확인하며, 이후 가격이 현재 가격보다 높은 경우를 찾아 매도하는 방식으로 접근했다. 즉, 각 날의 가격과 이후 가격들을 비교하여 최적의 매도 시점을 찾으려는 방식이었다.
T = int(input())
res = []
for i in range(T):
N = int(input())
SP = list(map(int, input().split()))
gain = 0
stock = 0
cnt = 0
for j in range(N):
if j == N - 1:
if stock > 0:
gain += (SP[j] * cnt) - stock
break
if SP[j] <= max(SP[(j+1):]):
stock += SP[j]
cnt += 1
else:
if stock == 0:
break
gain += (SP[j] * cnt) - stock
cnt = 0
stock = 0
res.append(gain)
for i in range(len(res)):
print(res[i])🔹 문제점
max(SP[(j+1):])를 반복적으로 호출하면서 시간 초과가 발생함 (O(N^2)).- 전체 리스트를 매번 확인하는 방식이 비효율적이므로, 다른 접근 방식이 필요함.
2. 거꾸로 접근하는 방법
시간 초과 문제를 해결하기 위해 뒤에서부터 주가를 확인하는 방식으로 접근하면 O(N)의 시간 복잡도로 해결할 수 있다.
🔹 나의 깨달음
시간 초과 문제를 해결하기 위해 다양한 방법을 고민하다가, 주식을 언제 파는지가 핵심이라는 점을 깨달았다. 가장 비싼 날에 팔아야 한다는 점을 고려하면, 오히려 뒤에서부터 탐색하는 것이 더 효과적이라는 것을 알게 되었다.
🔹 개선된 코드
T = int(input())
res = []
for i in range(T):
N = int(input())
SP = list(map(int, input().split()))
max_number = 0 # 최댓값을 저장할 변수
gain = 0 # 총 이익
for j in range(N-1, -1, -1): # 거꾸로 탐색
if SP[j] > max_number:
max_number = SP[j]
else:
gain += max_number - SP[j]
res.append(gain)
for i in range(len(res)):
print(res[i])🔹 코드 설명
- 리스트를 뒤에서부터 탐색한다.
max_number변수를 사용해 현재까지의 최대 가격(판매가) 을 저장한다.- 현재 가격이
max_number보다 작다면, 해당 가격에 매수 후(max_number - SP[j])만큼 이익을 추가한다. - 현재 가격이
max_number보다 크면,max_number를 갱신한다. - 모든 탐색이 끝나면 결과를 출력한다.
시간 복잡도 분석
| 접근 방식 | 시간 복잡도 | 이유 |
|---|---|---|
| 기존 코드 | O(N^2) | max() 호출을 N번 반복 |
| 개선된 코드 | O(N) | 리스트를 한 번만 순회 |
개선된 코드에서는 N번만 순회하며 최대값을 갱신하므로, 최적의 성능을 보장한다.
✨ 핵심 정리
- 처음에는
max()함수를 반복적으로 호출하면서 시간 초과가 발생하는 문제를 겪었다. - 이후 거꾸로 탐색하면서 최적의 매도 시점을 설정하는 방법을 떠올렸고, 이를 적용하여
O(N)의 효율적인 코드로 개선했다. - 그리디 알고리즘을 활용하여 최적의 선택을 반복적으로 수행한다.
- 뒤에서부터 탐색하면서 최대 매도가격을 갱신하면 최적해를 찾을 수 있다.
- 시간 초과를 피하기 위해
O(N^2)접근 대신O(N)접근을 사용한다.
