문제 링크
문제 요약
Lesson 9의 Maximum slice problem 에 해당한다.주어지는 배열의 각 value들은 주식의 가격에 해당하고 배열의 인덱스는 day에 해당한다. 따라서, A[0]에 25000원에 구매하고 A[2]에 28000원에 판매했다면, day 0에 구매 day 2에 판매해 3000원에 profit을 얻는 것이다. 만약, 값이 음수라면 loss에 해당한다.
이때, 최대 profit을 구해 return하면 된다.
더 자세한 내용들은 위의 링크로 이동하여 확인해보길 바란다.
문제 풀이 #1 - 시간 복잡도 O(n) 77%
def solution(A):
# Implement your solution here
if len(A) < 2:
#길이가 0 또는 1이라면 그냥 1
return 0
minIdx = A.index(min(A)) #최소값이 저장되어있는 index 찾기
#print(maxIdx)
profit =0
tmp = 0
for i in range(minIdx+1, len(A)):
profit = A[i] - A[minIdx]
if profit > tmp :
tmp = profit
#print(profit)
return tmp 문제 풀이 #2 - 시간 복잡도 O(n)
def solution(A):
# Implement your solution here
if len(A) < 2:
#길이가 0 또는 1이라면 그냥 1 return
return 0
#minIdx = A.index(min(A)) #최소값이 저장되어있는 index 찾기
#print(maxIdx)
maxVal=0
minVal = A[0]
for i in range(1, len(A)):
if minVal > A[i]:
minVal = A[i]
profit = A[i] - minVal
if profit > maxVal :
maxVal = profit
return maxVal📌 고려해야할 점
- 만약, 들어온 배열의 길이가 2보다 작다면, 주식을 사고 팔 수가 없기 때문에 max profit은 0에 해당한다.
위의 예외 처리를 처음에 생각해주지 못했다. - 첫 번째, index의 값을 최소로 우선 저장해두고 for문을 돌면서 최소값을 비교하여 현재 인덱스의 value가 저장된 minVal보다 작으면 값을 대체해준다.
- 또한, profit을 계산하여 maxVal을 계쏙해서 update 해준다.
🙄 느낀 점
어차피 max profit을 구하는 문제라서 리스트에서 최소값을 갖고 있는 인덱스를 구하고 그 이후에서 max value와의 차이를 구해 답을 구하two increasing subsequences(문제 풀이 #1) 하지만, 배열 내에서two increasing subsequences가 있는 경우에서 minVal이 고정되어 있어 오류가 났다. 따라서, 문제 풀이 #2와 같이 minVal과 maxVal을 계속 update해주는 방식을 이용해야한다.
