Python으로 배열에서 가장 가까운 왼쪽·오른쪽 작은 요소 간 최대 차이 구하기

정수로 이루어진 배열이 주어졌을 때, 배열의 각 요소에 대해 가장 가까운 왼쪽 작은 값과 가장 가까운 오른쪽 작은 값 사이의 최대 절대 차이를 구하는 문제를 살펴보겠습니다.

만약 어떤 요소의 왼쪽이나 오른쪽에 더 작은 요소가 존재하지 않는다면, 해당 방향의 작은 값은 0으로 간주합니다.

문제 예시

입력 배열이 다음과 같다고 가정해 보겠습니다.

A = [3, 5, 9, 8, 8, 10, 4]

이 경우 출력 결과는 4가 됩니다. 그 이유는 다음과 같습니다.

왼쪽 작은 요소 배열 L = [0, 3, 5, 5, 5, 8, 3]
오른쪽 작은 요소 배열 R = [0, 4, 8, 4, 4, 4, 0]
최대 절대 차이 |L[i] - R[i]| = |8 - 4| = 4

해결 접근 방법

이 문제는 스택(Stack) 자료구조를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. left_small_element() 함수 정의

배열 A와 결과를 저장할 임시 리스트 temp를 매개변수로 받습니다.

n := 배열 A의 크기
stack := 새로운 빈 리스트 생성
i를 0부터 n-1까지 반복합니다.
- 스택이 비어 있지 않고, 스택의 top 원소가 A[i]보다 크거나 같으면 pop하여 제거합니다.
- 스택이 비어 있지 않다면 temp[i]에 스택의 top 원소를 저장합니다.
- 스택이 비어 있다면 temp[i]에 0을 저장합니다.
- 현재 값 A[i]를 스택에 push합니다.

2. 메인 로직에서 수행할 작업

n := 배열 A의 크기
left := 크기 n의 리스트를 0으로 초기화
right := 크기 n의 리스트를 0으로 초기화
left_small_element(A, left) 호출 → 왼쪽 작은 요소 계산
left_small_element(뒤집은 A, right) 호출 → 오른쪽 작은 요소 계산
res := -1로 초기화
i를 0부터 n-1까지 반복하며 res := max(res, |left[i] - right[n-1-i]|) 갱신

Python 구현 코드

아래 예제 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.

def left_small_element(A, temp):
    n = len(A)
    stack = []
    for i in range(n):
        while(stack != [] and stack[len(stack)-1] >= A[i]):
            stack.pop()
        if(stack != []):
            temp[i] = stack[len(stack)-1]
        else:
            temp[i] = 0
        stack.append(A[i])

def find_maximum_difference(A):
    n = len(A)
    left = [0]*n
    right = [0]*n
    left_small_element(A, left)
    left_small_element(A[::-1], right)
    res = -1
    for i in range(n):
        res = max(res, abs(left[i] - right[n-1-i]))
    return res

A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

입력

[3, 5, 9, 8, 8, 10, 4]

출력

복잡도 분석

각 요소는 스택에 최대 한 번 push되고 한 번 pop되므로, 시간 복잡도는 O(n)입니다. 추가로 왼쪽/오른쪽 결과 배열과 스택을 저장하기 때문에 공간 복잡도 역시 O(n)입니다. 단순히 모든 요소마다 양방향을 탐색하는 O(n²) 브루트포스 방식보다 훨씬 효율적이라는 점이 이 알고리즘의 가장 큰 장점입니다.