파이썬으로 배열이 단조(Monotonic) 배열인지 확인하는 방법

이 글에서는 주어진 문제를 해결하기 위한 접근 방식과 구현 방법에 대해 알아보겠습니다.

문제 정의

정수 n개로 이루어진 배열 Arr이 주어졌을 때, 이 배열이 단조(monotonic) 배열인지 판별해야 합니다.

단조 배열이란 모든 요소가 끊임없이 증가하거나, 반대로 끊임없이 감소하는 배열을 의미합니다.

수학적으로 표현하면,

배열 A의 모든 i <= j에 대해 다음 조건을 만족하면 '증가하는' 배열입니다.

A[i] <= A[j]

반대로, 배열 A의 모든 i <= j에 대해 다음 조건을 만족하면 '감소하는' 배열입니다.

A[i] >= A[j]

따라서 여기서는 인접한 두 요소들이 위 두 조건 중 하나를 만족하는지 순차적으로 검사하는 방식으로 문제를 해결합니다.

그럼 실제 구현 예제를 살펴보겠습니다.

구현 예제

def isMonotonic(A):
   return (all(A[i] <= A[i + 1] for i in range(len(A) - 1)) or
      all(A[i] >= A[i + 1] for i in range(len(A) - 1)))
# main
A = [1,2,3,4,7,8]
print(isMonotonic(A))

출력 결과

True

위 코드에서 사용된 변수들은 아래 그림과 같이 전역 프레임(global frame)에 선언됩니다.

동작 원리

이 코드는 파이썬 내장 함수 all()과 제너레이터 표현식을 활용합니다. 먼저 배열이 단조 증가하는지 확인하고, 만약 그렇지 않다면 단조 감소하는지 검사합니다. 두 조건 중 하나라도 참이면 True를 반환하며, 배열의 모든 인접 요소를 한 번씩만 비교하므로 시간 복잡도는 O(n)으로 매우 효율적입니다.

결론

이 글에서는 파이썬을 이용해 배열이 단조 증가 또는 단조 감소하는지, 즉 단조(monotonic) 배열인지 판별하는 방법을 살펴보았습니다. 간단한 인접 요소 비교 논리만으로도 선형 시간 안에 문제를 손쉽게 해결할 수 있습니다.