파이썬으로 비감소 배열 판별하기 – 단 한 번의 수정으로 가능할까?

문제 개요

정수 n개로 이루어진 배열이 주어졌을 때, 최대 한 개의 요소만 수정하여 배열을 비감소(non-decreasing) 배열로 만들 수 있는지 확인하는 것이 이번 포스팅의 핵심입니다. 여기서 비감소 배열이란 모든 인덱스 i(1 <= i < n)에 대해 array[i] <= array[i + 1] 조건을 만족하는 배열을 의미합니다.

예를 들어 배열이 [4, 2, 3]이라면 정답은 true입니다. 첫 번째 요소인 4를 1로 바꾸기만 하면 [1, 2, 3]이 되어 비감소 배열을 만들 수 있기 때문입니다.

해결 접근 방법

이 문제는 그리디(Greedy) 방식으로 효율적으로 해결할 수 있습니다. 다음 단계를 따릅니다.

• 배열의 길이가 2 이하라면 true를 반환합니다.
• 수정 여부를 추적하기 위한 변수 ans := False로 초기화합니다.
• i를 0부터 (배열 길이 - 2)까지 반복하며 다음을 검사합니다.
  • arr[i] > arr[i + 1]인 경우:
    • ans가 이미 True라면 두 번째 위반이 발생한 것이므로 false를 반환하고, 그렇지 않으면 ans := True로 설정합니다.
    • i > 0인 경우, arr[i - 1] > arr[i + 1]이라면 arr[i + 1] := arr[i]로 값을 수정합니다.
• 반복이 끝나면 true를 반환합니다.

핵심 아이디어는 내림차순 위반이 발생했을 때, 앞의 값이 더 작도록 현재 요소를 조정하거나 필요 시 뒤의 값을 올려주는 방식으로 단 한 번의 수정 기회를 활용하는 것입니다.

파이썬 코드 예제

아래 구현을 살펴보면 동작 원리를 더 쉽게 이해할 수 있습니다.

class Solution(object):
    def checkPossibility(self, nums):
        if len(nums) <= 2:
            return True
        ans = False
        for i in range(len(nums)-1):
            if nums[i] > nums[i+1]:
                if ans:
                    return False
                else:
                    ans = True
                if i > 0:
                    if nums[i-1] > nums[i+1]: nums[i+1] = nums[i]
        return True

ob1 = Solution()
print(ob1.checkPossibility([4,2,3,5]))

입력

[4,2,3,5]

출력

True

[4, 2, 3, 5] 배열에서는 4보다 작은 2에서 한 번의 위반이 발생하지만, 4를 조정하면 비감소 배열이 되므로 결과는 True입니다. 이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 매우 효율적입니다.