Intuition

값이 올라가기 시작하는 지점부터 내려오는 지점까지의 길이의 최댓값을 구하는 문제이다. Literally 산을 찾으면 된다. 그러기 위해선 올라가는 부분과 내려가는 부분, 그리고 하산이 끝나는 지점을 특정시켜줄 수 있어야 한다.

Approach

올라가는 부분과 내려가는 부분의 길이를 count한 다음 하산이 끝난시점에서 max값을 결정시켜주는 일련의 작업을 반복하는 흐름으로 진행된다.

등산부분의 길이, 하산부분의 길이, 최댓값을 담을 변수를 선언 및 초기화한다.

    int up,down,max;
    up=down=max=0;

array의 연속된 두 원소($i,i+1$)의 값을 비교할 것이므로 (배열의 크기)-1만큼 순회한다.

    for (int i=0;i<arrSize-1;i++){
		...
    }

• 등산 및 하산 완료 파트
  산이 끝나는 지점을 특정시키고 지금까지 count된 up과 down의 길이를 통해 max값을 결정시키는 부분이다.
  산이 끝나는 지점은 우선, 다음 원소와 비교했을 때 그 값이 더 작아지지만 않으면 된다. 더 큰 값이 나오든, 같은 값이 나오든 상관없다는 뜻이다.
  그리고 앞서 등산하는 파트와 하산하는 파트가 있었기 때문에 up, down 변수가 0보다 큰 상태이다.
  그러나 이 부분은 산이 끝나는 지점이자 동시에 새로운 산이 시작하는 지점이 될 수도 있기 때문에
  다음 원소와 비교했을 때 그 값이 더 크다면 up 변수를 업데이트 해줘야한다. (ex. 1 5 1 3)

        if (!(arr[i]>arr[i+1])&&down){ // up 변수 미체크 사유는 후술
            if (max<up+down+1) max=up+down+1;
            up=down=0;
            if (arr[i]<arr[i+1]) up++; // 산이 끝나는 지점이자 동시에 시작하는 지점
        }

• 하산 파트
  기본적으로 다음 원소가 더 작아야한다. 또한, 이전에 등산 파트가 존재했어야 한다. 즉, up 변수가 0보다 커야한다.
  그리고 이렇듯 up 변수가 0보다 클때만 down 변수가 업데이트 되므로, 등산 및 하산 완료 파트를 체크할때 down 변수만 체크해주면 된다.
• 등산 파트
  다음 원소가 더 크다면 up변수를 업데이트 해주면 된다.
• 그 외
  1 3 5 5 와 같이 등산하다가 같은 숫자가 나온다든지, 산과 관련 없는 부분들도 존재하므로 따로 처리해줘야한다.

    for (int i=0;i<arrSize-1;i++){
        if (!(arr[i]>arr[i+1])&&down){ // 등산 및 하산 완료 파트
            if (max<up+down+1) max=up+down+1;
            up=down=0;
            if (arr[i]<arr[i+1]) up++;
        }
        else if (arr[i]>arr[i+1]&&up) down++; // 하산파트
        else if (arr[i]<arr[i+1]) up++; // 등산파트
        else up=down=0; // 그 외 
    }

그런데, 위 반복문이 (배열의 크기)-1만큼 순회하므로 1 5 1 과 같이 마지막 원소에서 산이 끝나게 되는 경우는 체크를 해줄 수가 없다.
따라서 마지막에, up down 변수를 체크해 최종적으로 max값을 결정지어준다.

    if (up>0&&down>0){
        if (max<up+down+1) max=up+down+1;
    }

Solution

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

Complexity

Time Complexity && Space Complexity

$O(N)$

교수님 풀이

two pointers를 이용한 풀이는 전반적 로직이 동일하고 교수님께서도 그리 좋은 풀이는 아니라고 언급하신 관계로 넘어가도록 한다.

이 풀이는 올라가는 부분의 길이와 내려가는 부분의 길이를 각각 세고 두 부분의 길이의 합이 가장 큰 곳을 찾는 방식으로 진행된다. up배열부터 살펴보겠다.
우선 최초 인덱스 up[0]은 0으로 시작한다.
4에서 2로 넘어갈 때에는 그 값이 증가하지 않으므로 그대로 0을 할당시켜준다.
2에서 3으로 넘어갈 때에는 값이 증가하므로 이전 인덱스보다 +1시킨 값을 할당시켜준다.
3에서 5도 마찬가지이다.
하지만 5에서 1은 다시 감소하므로 0을 다시 할당시켜준다.

down배열은 뒤에서부터 거꾸로 순회하면 된다.

    int *up=(int*)malloc(sizeof(int)*arrSize);
    int *down=(int*)malloc(sizeof(int)*arrSize);
    up[0]=0,down[arrSize-1]=0;
    int upCnt, downCnt;
    upCnt=downCnt=0;

    for (int i=1;i<arrSize;i++){
        if (arr[i-1]<arr[i]) upCnt++;
        else upCnt=0;
        up[i]=upCnt;

        if (arr[arrSize-i]<arr[arrSize-i-1]) downCnt++;
        else downCnt=0;
        down[arrSize-i-1]=downCnt;
    }

이제 배열을 순회하며 그 합이 가장 큰 곳을 찾으면 된다.
이때 주의할 점은 배열의 값이 0인 부분 즉, 아래 예시에서는 올라가는 파트는 맞으나 내려가는 파트는 아닌부분과 같이 산 모양 여부를 판단하기 위한 작업을 진행해주어야한다.

이를 위해선 up down 배열의 값이 0보다 큰지 확인해주면 된다.

    int max=0;
    for (int i=0;i<arrSize;i++){
        if (up[i]&&down[i]&&(up[i]+down[i]+1>max)) max=up[i]+down[i]+1;
    }

Solution

int longestMountain(int* arr, int arrSize){
    int *up=(int*)malloc(sizeof(int)*arrSize);
    int *down=(int*)malloc(sizeof(int)*arrSize);
    up[0]=0,down[arrSize-1]=0;
    int upCnt, downCnt;
    upCnt=downCnt=0;

    for (int i=1;i<arrSize;i++){
        if (arr[i-1]<arr[i]) upCnt++;
        else upCnt=0;
        up[i]=upCnt;

        if (arr[arrSize-i]<arr[arrSize-i-1]) downCnt++;
        else downCnt=0;
        down[arrSize-i-1]=downCnt;
    }

    int max=0;
    for (int i=0;i<arrSize;i++){
        if (up[i]&&down[i]&&(up[i]+down[i]+1>max)) max=up[i]+down[i]+1;
    }

    free(up), free(down);
    return max;
}

Complexity

Time Complexity && Space Complexity

$O(N)$

지적 및 질문 환영