Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 배열의 왼쪽·오른쪽 가장 가까운 작은 요소 간 최대 차이 구하기

개념

정수 배열이 주어졌을 때, 배열의 모든 요소에 대해 왼쪽에서 가장 가까운 더 작은 요소와 오른쪽에서 가장 가까운 더 작은 요소를 찾아 두 값의 절댓값 차이를 계산하고, 그중 최댓값을 구하는 것이 이 문제의 목표입니다.

만약 어떤 요소의 왼쪽이나 오른쪽에 더 작은 요소가 존재하지 않는다면 해당 값은 0으로 간주합니다. 예를 들어 가장 왼쪽에 있는 요소는 왼쪽에 더 작은 값이 없으므로 0으로 처리하며, 가장 오른쪽 요소 역시 오른쪽의 더 작은 값을 0으로 처리합니다.

예시 1

arr[] = {3, 2, 9}

출력:

2

왼쪽 더 작은 요소 LS[] = {0, 0, 2}
오른쪽 더 작은 요소 RS[] = {2, 0, 0}

최대 차이 = |LS[i] − RS[i]|의 최댓값 = |2 − 0| = 2

예시 2

arr[] = {3, 5, 9, 8, 8, 10, 4}

출력:

4

왼쪽 더 작은 요소 LS[] = {0, 3, 5, 5, 5, 8, 3}
오른쪽 더 작은 요소 RS[] = {0, 4, 8, 4, 4, 4, 0}

최대 차이 = |8 − 4| = 4

풀이 방법

1. 단순한 접근법 — O(n²)

모든 요소에 대해 왼쪽과 오른쪽에서 가장 가까운 더 작은 요소를 각각 찾은 뒤, 그 차이를 계산하여 최댓값을 갱신하는 방식입니다. 구현은 직관적이지만 이중 반복문이 필요해 시간 복잡도가 O(n²)로 비효율적입니다.

2. 효율적인 접근법 — 스택 활용, O(n)

스택을 사용하면 선형 시간 안에 문제를 해결할 수 있습니다. 핵심 아이디어는 하나의 함수로 왼쪽 더 작은 요소와 오른쪽 더 작은 요소를 모두 계산할 수 있다는 점입니다. 배열을 한 번 뒤집으면 '오른쪽 더 작은 요소 찾기' 문제가 '왼쪽 더 작은 요소 찾기' 문제와 동일해지기 때문입니다.

입력 배열을 Array[], 배열의 크기를 n이라고 가정합니다.

① 왼쪽 더 작은 요소 구하기

  • 빈 스택 S와 결과 배열 LS[]를 준비합니다.
  • i를 0부터 n−1까지 증가시키며 각 요소 Array[i]에 대해 다음을 수행합니다.
    • 스택 S가 비어 있지 않고 S의 top이 Array[i]보다 크거나 같으면 pop합니다.
    • 스택이 비어 있다면 Array[i]보다 작은 앞선 요소가 없으므로 LS[i] = 0입니다.
    • 그렇지 않다면 가장 가까운 더 작은 값은 스택의 top이므로 LS[i] = S.top()입니다.
    • Array[i]를 스택에 push합니다.

② 오른쪽 더 작은 요소 구하기

  • 먼저 배열 Array[]를 뒤집습니다. 배열을 뒤집으면 오른쪽 더 작은 요소가 왼쪽 더 작은 요소 문제로 바뀝니다.
  • 배열 RRS[]를 만들고 위의 ① 단계를 그대로 반복하여 RRS를 채웁니다(LS 대신).
  • 결괏값 result를 −1로 초기화한 뒤, 모든 요소 Array[i]에 대해 다음을 수행합니다. 뒤집힌 배열 기준으로 Array[i]의 오른쪽 더 작은 값은 RRS[n−i−1]에 저장되어 있으므로, result = max(result, |LS[i] − RRS[n−i−1]|)로 갱신합니다.

C++ 구현 예제

// C++ 프로그램: 배열의 각 요소에 대해 왼쪽/오른쪽
// 더 작은 요소 간의 최대 차이를 구합니다
#include<bits/stdc++.h>
using namespace std;

// Array[0..n1-1]의 모든 요소에 대해 왼쪽에서 가장 가까운
// 더 작은 값을 계산하여 SE1[0..n1-1]에 저장합니다
void leftSmaller(int Array[], int n1, int SE1[]){
    // 빈 스택 생성
    stack<int>S1;
    // 모든 배열 요소를 순회하며 각 요소의
    // 가장 가까운 더 작은 값을 계산
    for (int i=0; i<n1; i++){
        // 스택의 top이 Array[i]보다 크거나 같은 동안 제거
        while (!S1.empty() && S1.top() >= Array[i])
            S1.pop();
        // 현재 요소보다 작은 요소를 저장
        if (!S1.empty())
            SE1[i] = S1.top();
        // 스택의 모든 요소가 Array[i]보다 큰 경우
        else
            SE1[i] = 0;
        // 현재 요소를 스택에 push
        S1.push(Array[i]);
    }
}

// 왼쪽/오른쪽 더 작은 요소 간의 최대 차이를 반환하는 함수
int findMaxDiff(int Array[], int n1){
    int LS1[n1]; // 왼쪽 더 작은 요소를 저장
    // 각 요소의 왼쪽 더 작은 요소를 계산
    leftSmaller(Array, n1, LS1);
    // 각 요소의 오른쪽 더 작은 요소를 계산
    // 먼저 배열을 뒤집은 뒤 동일한 과정을 수행
    int RRS1[n1]; // 뒤집힌 배열의 결과를 저장
    reverse(Array, Array + n1);
    leftSmaller(Array, n1, RRS1);
    // LS1과 RRS1 사이의 최대 절댓값 차이를 계산
    // 뒤집힌 배열에서 Array[i]의 오른쪽 더 작은 값은
    // RRS1[n1-i-1]에 위치
    int result1 = -1;
    for (int i=0 ; i< n1 ; i++)
        result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
    // LS1과 RRS1 간의 최대 차이를 반환
    return result1;
}

// 드라이버 코드
int main(){
    int Array[] = {3, 5, 9, 8, 8, 10, 4};
    int n = sizeof(Array)/sizeof(Array[0]);
    cout << "Maximum diff : "
         << findMaxDiff(Array, n) << endl;
    return 0;
}

실행 결과

Maximum diff : 4

복잡도 분석

이 알고리즘에서 각 요소는 스택에 최대 한 번 push되고 한 번 pop되므로 전체 시간 복잡도는 O(n)이며, 왼쪽·오른쪽 결과 배열과 스택을 위해 O(n)의 추가 공간이 필요합니다. 단순한 O(n²) 완전 탐색 방식과 비교했을 때, 스택 기반 접근법은 배열의 크기가 커질수록 압도적으로 빠른 성능을 보여줍니다.