DataScience trainee

Leetcode 1526. Minimum Number of Increments on Subarrays to Form a Target Array in Python3

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 에 해당하는 문제입니다.