배열이 하나 주어졌을 때, 자신의 왼쪽에 있는 모든 요소는 자신보다 작고, 오른쪽에 있는 모든 요소는 자신보다 큰 지점 역할을 하는 요소를 찾아야 합니다. 그러한 요소가 존재하면 해당 인덱스를 반환하고, 존재하지 않으면 -1을 반환합니다.
예를 들어 입력 배열이 [6, 2, 5, 4, 7, 9, 11, 8, 10]이라면, 인덱스 4에 있는 값 7이 왼쪽 요소들(6, 2, 5, 4)보다 크고 오른쪽 요소들(9, 11, 8, 10)보다 작으므로 결과는 4가 됩니다.
문제 해결 접근법
이 문제는 왼쪽에서부터의 누적 최댓값과 오른쪽에서부터의 누적 최솟값을 활용하면 두 번의 선형 순회만으로 O(n) 시간에 효율적으로 해결할 수 있습니다. 알고리즘은 다음 단계로 진행됩니다.
n := 배열 arr의 길이
maximum_left := 크기가 n인 배열을 생성하고, 각 인덱스 i를 기준으로 왼쪽 부분 배열의 최댓값을 저장
maximum_left[0] := 음의 무한대(-inf)
i를 1부터 n-1까지 반복하며 maximum_left[i] := max(maximum_left[i-1], arr[i-1]) 계산
minimum_right := 양의 무한대(inf)
i를 n-1부터 0까지 역순으로 반복:
만약 maximum_left[i] < arr[i] 이고 minimum_right > arr[i]라면, 현재 인덱스 i를 반환
그렇지 않으면 minimum_right := min(minimum_right, arr[i])로 갱신
조건을 만족하는 요소가 없다면 -1을 반환
예시 구현
아래 파이썬 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
def get_element(arr):
n = len(arr)
maximum_left = [None] * n
maximum_left[0] = float('-inf')
for i in range(1, n):
maximum_left[i] = max(maximum_left[i-1], arr[i-1])
minimum_right = float('inf')
for i in range(n-1, -1, -1):
if maximum_left[i] < arr[i] and minimum_right > arr[i]:
return i
minimum_right = min(minimum_right, arr[i])
return -1
arr = [6, 2, 5, 4, 7, 9, 11, 8, 10]
print(get_element(arr))입력
[6, 2, 5, 4, 7, 9, 11, 8, 10]
출력
4
동작 원리
maximum_left 배열은 각 위치를 기준으로 왼쪽에 있는 값들 중 최댓값을 미리 계산해 둡니다. 이후 오른쪽 끝에서부터 순회하면서 minimum_right(오른쪽 부분의 최솟값)를 유지하는데, 어떤 인덱스 i에서 "왼쪽 최댓값 < arr[i]"이면서 "오른쪽 최솟값 > arr[i]"가 동시에 성립하면 그 위치가 바로 우리가 찾는 요소입니다. 이 방식은 시간 복잡도 O(n), 공간 복잡도 O(n)으로 대규모 배열에서도 매우 효율적으로 동작합니다.