Minimum Number of Increments on Subarrays to Form a Target Array
개요
- 이번 포스팅은 파이썬 코딩테스트 연습문제 풀이입니다.
Leetcode
에 공개된 예제이며 링크는 아래와 같습니다.
https://leetcode.com/problems/minimum-number-of-increments-on-subarrays-to-form-a-target-array/
코드
def minNumberOperations(self, target: List[int]) -> int:
# 우선 target을 한번씩 탐색하여 status list를 만든다 -> n번 시행
# 이 때 가장 최초 status는 up이 되고 가장 마지막 status는 down이 되야하므로 처음과 마지막 값을 0으로 지정한다.
# 만들면서 status가 변하는 부분을 peak으로 따로 list를 저장한다
# 홀수번째 peak는 under peak이고 짝수번째 peak는 upper peak이다
# peak를 한번 씩 탐색하여 각자 대응하는 upper peak와 under peak를 빼주고 answer에 더해준다 -> n번 독립시행
# peak를 다시한번 탐색하여 under peak중 가장 큰 수를 answer에 더해준다 -> n번 독립시행
# 결과적으로 O(n)으로 마무리 가능하다.
p_value = 0
p_status = 'up'
peak = []
for idx in range(len(target)):
c_value = target[idx]
if c_value > p_value:
c_status = 'up'
elif c_value < p_value:
c_status = 'down'
if p_status != c_status:
peak.append(target[idx-1])
# value 업데이트
p_value = c_value
p_status = c_status
# 마지막 idx 예외처리
if idx == (len(target)-1):
c_status = 'down'
if p_status != c_status:
peak.append(target[idx])
# end for
under_peak = 0
answer = 0
for idx, value in enumerate(peak):
if idx % 2 == 0:
upper_peak = value
answer += upper_peak - under_peak
else:
under_peak = value
return answer
마치며
이번 포스팅은 Leetcode
에 존재하는Greedy
알고리즘 중 난이도 Hard 에 해당하는 문제입니다.