[C] LeetCode 845. Longest Mountain In Array

 

문제

번역

arr 배열을 mountain array라고 부르려면 다음 조건을 만족해야 한다.

1. 배열의 길이가 3 이상이어야 하고

2. 어떤 인덱스 i에 대해서 0번 원소부터 i번 원소까지 단조 증가해야 하며

3. i번 인덱스부터 배열의 끝까지 단조 감소해야 한다.

 

주어진 정수 배열 arr에서 가장 긴 mountain 부분 배열의 길이를 반환하고, 없다면 0을 반환해라.

접근 방법과 소스코드

처음에는 매 인덱스마다 검사하는 로직을 작성했다.

 

현재 인덱스 \(i\)에 도착했을때, 포인터 \(l\)은 왼쪽으로 내려가면서 \(l\)부터 \(i\)까지 단조 증가하는지 검사하고,

포인터 \(r\)은 오른쪽으로 올라가면서 \(i\)부터 \(r\)까지 단조 감소하는지 검사한다.

포인터가 최대한 단조 증가/감소하는 위치까지 내려가게 만든 다음, 반복문이 끝나면 해당 길이가 기존에 나온 길이중 가장 긴 길이인지 검사하고 업데이트 하게 작성했다.

또한, 검색 효율을 위해서 다음 인덱스를 \(r+1\)로 지정했다. 

 

int longestMountain(int* arr, int arrSize) {
    int maxi = 0; int l=0, r=0,i=1;
    while(i >= 0 && i < arrSize) {
        l = i; r = i;
        while ( 0 < l && arr[l-1] < arr[l]) l--;
        while ( r < arrSize-1 && arr[r] > arr[r+1]) r++;
        maxi = ((r-l+1) >= 3 && (i!=l && r!=i) &&maxi < (r-l+1)) ? r-l+1 : maxi;
        i = r+1;
    }
    return maxi;
}

 

이렇게 풀고 실행하니 통과는 되었다. 그리고 아래와 같은 결과를 얻었다.

 

실행 속도는 처참했다.

가만 다시 생각해보니, \(i\)를 \(r+1\)로 옮긴다 해도, 최악의 경우 \(l\)은 매번 0번 인덱스까지 탐색할 수 밖에 없다.

즉 검색 효율은 그대로란 이야기다.

 

더 효율적인 방법이 있을거 같아서 다시 고민해봤다.

그냥 배열을 순회하면서 증가하는 구간과 감소하는 구간을 세서 매번 업데이트 해주면 되는거 아닌가 싶었다.

또 감소하는 구간이다가 증가하거나 아니면 값이 유지되는 구간인 경우 구간을 세는것을 초기화하면 되지 않을까 싶었다.

 

int longestMountain(int* arr, int arrSize) {
    short up = 0, down = 0;
    short maxi = 0;
    for(int i = 1; i<arrSize; i++) {
        if(arr[i-1] < arr[i]) {
            up++;
            if(down != 0) { up = 1; down =0; }
        }
        else if(arr[i-1] > arr[i]) down++;
        else { up=0; down=0;}
        if(up > 0 && down > 0) maxi = (maxi < (down+up+1)) ? down+up+1 : maxi;
    }
    return maxi;
}

 

그렇게 해서 이러한 코드가 나왔다.

변수 타입이 short인 이유는 배열의 길이가 10000 정도라서 short의 범위 내에서 충분히 할 수 있을거라 생각했다.

 

실행하니 실행시간이 매우 짧게 나왔다.

문제에서 요구했던 \(O(n)\)의 시간복잡도와 \(O(1)\)의 공간복잡도로 문제를 해결했다.