Baekjoon-2491) 수열

백준 사이트 URL : https://www.acmicpc.net/problem/2491

문제분석

입력 : 길이 n과 최대 길이와 n개의 정수

출력 : 연속된 증가 혹은 감소 수열의 가장 긴 길이를 출력한다.

아이디어

1. 감소와 증가 수열의 기록을 저장할 변수를 통해 한번의 탐색으로 해결한다.

2. 같은 경우는 두 변수를 증가 시킨다. 그 외는 경우에 따라 증가의 길이, 감소의 길이를 각각 증가 시킨다.

3. 길이를 비교하여 최대 길이를 

소스 코드

#include<cstdio>
 
int main() {
    int n, res = 1, pre = 0, num;
    scanf("%d", &n);
    int len_1 = 1, len_2 = 1;
    scanf("%d", &pre);
    n--;
 
    while (n--) {
        scanf("%d", &num);
        if (pre < num) {
            len_1++;
            res = len_1 > res ? len_1 : res;
            len_2 = 1;
        }
        else if(pre>num){
            len_2++;
            res = len_2 > res ? len_2 : res;
            len_1 = 1;
        }
        else {
            len_1++;
            len_2++;
            res = len_1 > res ? len_1 : res;
            res = len_2 > res ? len_2 : res;
        }
        pre = num;
    }
    
    printf("%d\n", res);
    return 0;
}

분석

 - 입력을 받으면서 길이를 구하고 바로 비교를 통해 나오기 때문에 O(n)의 시간복잡도를 갖는다.

 - 배열을 통해 저장하거나 그러지않기 때문에 O(1)의 공간복잡도를 갖는다.

[오류나 제가 생각하지 못한 부분에 있어서 개선사항은 코멘트를 달아주시면 감사하겠습니다.]