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

C++로 배열에서 가장 긴 산(Mountain) 부분 배열 찾기

문제 정의

정수 배열 A의 연속된 부분 배열 B가 다음 두 조건을 만족하면 이를 '산(mountain)'이라고 부릅니다.

  • B의 크기는 3 이상이어야 합니다.
  • 0 < i < B.length - 1을 만족하는 인덱스 i가 존재하여, B[0] < B[1] < ... < B[i] > B[i+1] > ... > B[B.length - 1] 형태여야 합니다. 즉, 처음에는 값이 계속 증가하다가 꼭대기를 지난 후 계속 감소하는 모양이어야 합니다.

정수 배열 A가 주어졌을 때, 가장 긴 산의 길이를 구하는 것이 목표입니다. 만약 산이 하나도 존재하지 않는다면 0을 반환합니다.

예를 들어 입력이 [2, 1, 4, 7, 3, 2, 5]라면 결과는 5입니다. 이때 가장 긴 산은 [1, 4, 7, 3, 2]이며, 그 길이는 5입니다.

알고리즘 접근 방법

배열을 한 번 순회하면서 오르막 구간과 내리막 구간을 차례로 찾아내는 방식으로 문제를 해결할 수 있습니다. 단계별 절차는 다음과 같습니다.

  • ret := 0으로 초기화하고, n := 배열 a의 크기로 설정합니다.
  • i를 0부터 n - 1까지 반복하되, 매 반복이 끝나면 i를 j + 1로 갱신합니다.
    • j := i로 초기화하고, down := false, up := false로 설정합니다.
    • j + 1 < n이고 a[j + 1] > a[j]인 동안 up := true로 설정하고 j를 1씩 증가시켜 오르막 구간을 진행합니다.
    • up이 true이고 j + 1 < n이며 a[j + 1] < a[j]인 동안 down := true로 설정하고 j를 1씩 증가시켜 내리막 구간을 진행합니다.
    • up과 down이 모두 true라면 유효한 산이므로 ret := max(j - i + 1, ret)으로 갱신하고, 다음 탐색을 위해 j를 1 감소시킵니다.
  • 모든 순회가 끝나면 ret을 반환합니다.

핵심 아이디어는 각 시작 위치에서 최대한 멀리까지 오르막을 먼저 진행한 뒤, 이어지는 내리막을 진행하는 것입니다. 오르막과 내리막이 모두 존재해야만 유효한 산이 되며, 내리막이 끝난 지점부터 다음 탐색을 이어가기 때문에 전체 시간 복잡도는 O(n)입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    int longestMountain(vector<int>& a) {
        int ret = 0;
        int n = a.size();
        int j;
        for(int i = 0; i < n; i = j + 1){
            j = i;
            bool down = false;
            bool up = false;
            while(j + 1 < n && a[j + 1] > a[j]) {
                up = true;
                j++;
            }
            while(up && j + 1 < n && a[j + 1] < a[j]){
                down = true;
                j++;
            }
            if(up && down){
                ret = max(j - i + 1, ret);
                j--;
            }
        }
        return ret;
    }
};
main(){
    vector<int> v = {2,1,4,7,3,2,5};
    Solution ob;
    cout << (ob.longestMountain(v));
}

입력

[2,1,4,7,3,2,5]

출력

5