[leetCode] 1827. Minimum Operations to Make the Array Increasing (Python)

▼ 문제 바로가기 (링크) ▼ 

https://leetcode.com/problems/minimum-operations-to-make-the-array-increasing/

Minimum Operations to Make the Array Increasing - LeetCode

---

1개 이상의 정수를 가지는 정수 배열 nums가 주어진다. 

값이 증가하는 배열을 만드려고 할 때, (무조건 이전 인덱스보다 커야 함)

각 요소를 한 번에 하나만 1씩 증가시킬 수 있다면

최소 몇 번 연산해야 하는지 정수로 반환하는 문제. 

 

# Time Limit Exceeded : Runtime: 4096 ms

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        tmp = nums[0]
        cnt = 0
        
        if len(nums) == 1:
            return 0
        
        else:
            for i in range(1, len(nums)):
                while nums[i] <= tmp:
                    nums[i] += 1
                    cnt += 1
                tmp = nums[i]
            return cnt

정상적으로 동작하지만 실행 시간이 너무 길어서 히든 케이스를 통과하지 못했다.

제출 전 미리 돌려본 결과 4096ms가 나왔다.

 

나이브하게 cnt를 1씩 증가하니 그만큼 반복문이 실행되고

값이 큰 값이 여러 개 담긴 리스트의 경우 너무 오래 걸렸다.

증가시켜야 하는 수를 마이너스 연산으로 구하도록 고쳐보았다.

 

# 개선한 코드! Runtime: 4096 ms  >> Runtime: 42 ms !

class Solution:
    def minOperations(self, nums: List[int]) -> int:
        tmp = nums[0]  # 인덱스 순서대로 값 담는 임시 변수 
        cnt = 0 
        
        if len(nums) == 1:
            return 0
        
        else: # cnt 연산에 영향 주는 변수는 나중에 값 변경(재할당)
            for i in range(1, len(nums)): 
                if nums[i] <= tmp:   
                    cnt += ((tmp - nums[i]) + 1) # 이전 값과의 차이만큼 +
                    nums[i] += ((tmp - nums[i]) + 1) # 증가시킨 값 재할당
                    tmp = nums[i]
                tmp = nums[i]   
            return cnt

차근차근 테스트 케이스의 계산 값을 주석으로 적어가며 작성했더니 성공했다!

엄청난 속도 차이...! 고쳐나가는 게 재밌긴 한데.. 시험 볼 때 그러면 오래 걸려서

안 좋을 테니 한 번에 효율적으로 작성하는 연습을 해나가야겠다.