[알고리즘] 특정 수열에서 양 옆 최대값을 O(1)로 구해보자!

✏️ 알고리즘 개요

알고리즘 문제를 풀다보면 특정 수열에서 i번째 원소를 기준으로 왼쪽 혹은 오른쪽 원소들에 대해 최대값을 구해야하는 경우가 종종 있다.

 

아래와 같이 단순하게 왼쪽, 오른쪽 원소들에 대해 반복문을 통해 최대값을 구하는 것을 생각해볼 수 있다.

int[] arr = new int[]{5,9,6,2,1,4,5,6,8,10,4};

for(int i=0; i<arr.length; i++) {
    //왼쪽 최대값
    int leftMaxValue = 0;
    for(int j=i-1; j>=0; j--) {
        leftMaxValue = Math.max(leftMaxValue, arr[j]);
    }

    //오른쪽 최대값
    int rightMaxValue = 0;
    for(int j=i+1; j<arr.length; j++) {
        rightMaxValue = Math.max(rightMaxValue, arr[j]);
    }
}

 

그러나 수열의 길이가 매우 길어지고, 찾아야하는 원소의 개수가 많아질수록 위와 같은 반복문은 매우 긴 시간복잡도를 가지게 된다. O(N^2)

 

이런 상황에서 최대값을 O(1)로 탐색하기 위해서는 누적합 원리를 사용하는 것으로 시간복잡도를 줄일 수 있다.

우리가 원하는 것은 i번째 원소를 기준으로 왼쪽, 오른쪽에 나오는 원소 중 최대값을 탐색하는 것이다.

첫 번째로 이러한 최대값을 기록하기 위한 배열을 따로 선언해보자.

int[] arr = new int[]{5,9,6,2,1,4,5,6,8,10,4};

int[] left = new int[arr.length];
int[] right = new int[arr.length];

 

각각의 left, right 배열은 i번째 원소에서 나올 수 있는 최대값을 기록한다.

두 번째는 이 배열의 원소를 채우는 과정으로 이루어지게 된다.

//왼쪽에서부터 최대값 탐색
left[0] = arr[0];
for(int i=1; i<arr.length; i++) {
    left[i] = Math.max(arr[i], left[i-1]);
}

//오른쪽에서부터 최대값 탐색
right[arr.length-1] = arr[arr.length-1];
for(int i=arr.length-2; i>=0; i--) {
    right[i] = Math.max(arr[i], right[i+1]);
}

위 코드를 보면 알 수 있듯, 마치 누적합을 구하는 것처럼 현재 원소와 이전 원소의 크기를 비교하여 각각의 left[i], right[i]를 구한다.

 

이러한 전처리 과정은 O(N)으로 왠만한 수열 길이에 대해서는 효율적으로 탐색할 수 있다.

 

그럼 이제 i원소에 대해 왼쪽, 오른쪽에 나오는 최대값을 탐색하는 것은 전처리된 left, right배열을 참조하는 것으로 O(1) 시간복잡도로 구할 수 있을 것이다.

for(int i=0; i<arr.length; i++) {
    //i원소의 왼쪽 최대값
    System.out.print(i-1 == -1 ? "첫번째 원소" : left[i-1] + " : ");
    //i원소의 오른쪽 최대값
    System.out.println(i+1 == arr.length ? "마지막 원소" : right[i+1]);
}

 

이러한 방식은 프리픽스/서픽스 최대값이라고 불리우는 것 같다.

또한 비슷한 개념으로 "모노톤 스택"이라는 스킬도 있는데 이후에 같이 알아보며 차이에 대해서 설명해보고자 한다.

---

⚠️ 한계점

이러한 방식은 특정 구간(x ~ y)에서의 최대/최소값을 구하는 방식으로, 임의 구간에서 최대/최소값을 찾는 문제에서는 적용할 수가 없다.

만약 적용한다 하더라도 매번 새롭게 left,right 배열을 탐색해야할 것이므로 시간복잡도가 매우 커지게 된다.

이러한 한계점에 대한 대안으로는 세그먼트 트리를 활용하는 것이다. 조금 더 상위개념으로 배열을 트리 구조로 나누어 구간 쿼리에 적합한 자료구조다.

---

🗒️ 연습 문제

https://www.acmicpc.net/problem/14719

 

해당 문제에 대한 풀이가 궁금하다면 아래 소스코드를 참조하면 좋을 것 같다.

import java.io.*;
import java.util.*;

//BOJ_14719
public class Main {
    static int h, w, res;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        h = Integer.parseInt(st.nextToken());
        w = Integer.parseInt(st.nextToken());

        /**
         * i번째 열에서 채워져야 하는 빗물의 칸 수 == Math.min(왼쪽 최대값, 오른쪽 최대값)
         * 전제조건 : 현재 칸 수 보다 왼쪽/오른쪽 최대값들이 커야함.
         * 사용할 수 있는 스킬 : 현재 i원소의 왼쪽/오른쪽 최대값을 구하기 위한 누적합
         * **/
        int[] arr = new int[w];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<w; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //왼쪽 최대값 배열
        int[] leftMax = new int[w];
        leftMax[0] = arr[0];
        for(int i=1; i<w; i++) {
            leftMax[i] = Math.max(arr[i], leftMax[i-1]);
        }

        //오른쪽 최대값 배열
        int[] rightMax = new int[w];
        rightMax[w-1] = arr[w-1];
        for(int i=w-2; i>=0; i--) {
            rightMax[i] = Math.max(arr[i], rightMax[i+1]);
        }

        for(int i=1; i<arr.length-1; i++) {
            if(leftMax[i-1] < arr[i] || rightMax[i+1] < arr[i]) continue;
            res += Math.min(leftMax[i-1], rightMax[i+1]) - arr[i];
        }

        System.out.println(res);

    }
}