JUNGOL 실력키우기 1998 : 수열

0에서부터 9까지의 숫자로 이루어진 N개의 숫자가 나열된 수열이 있다. 그 수열 안에서 연속해서 커지거나(같은 것 포함),

혹은 연속해서 작아지는(같은 것 포함) 수열 중 가장 길이가 긴 것을 찾아내어 그 길이를 출력하는 프로그램을 작성하라.

 

예를 들어 수열 1 2 2 4 4 5 7 7 2 의 경우에는 1≤2≤2≤4≤4≤5≤7≤7 이 가장 긴 구간이 되므로 그 길이 8을 출력한다. 

수열 4 1 3 3 2 2 9 2 3 의 경우에는 3≥3≥2≥2 가 가장 긴 구간이 되므로 그 길이 4를 출력한다. 

또 1 5 3 6 4 7 1 3 2 9 5 의 경우에는 연속해서 커지거나 작아지는 수열의 길이가 3 이상인 경우가 없으므로 

2를 출력하여야 한다.

 

첫째 줄에는 수열의 길이 N이 주어지고, 둘째 줄에는 N개의 숫자가 빈칸을 사이에 두고 주어진다.
N은 1 이상 100,000 이하의 정수이다.

첫째 줄에 가장 긴 길이를 출력한다.

9 1 2 2 4 4 5 7 7 2

8

9 4 1 3 3 2 2 9 2 3

4

11 1 5 3 6 4 7 1 3 2 9 5

2

---

이번 문제는 상당히 간단하게 해결할 수 있습니다. 가장 긴 수열을 출력하는 게 아닌 가장 긴 수열의 길이를 출력하라는 문제이기 때문에 입력되는 값을 실제로 저장할 필요도 없습니다. 단순하게 이전 값과 현재 값만 알면 비교를 통해 수열을 만들 수 있습니다.

점점 커지는 수열에서 가장 긴 값과 점점 작아지는 수열에서 가장 긴 값중 더 큰 값을 출력하면 되는 문제입니다.

#include <iostream>
 
using namespace std;
 
#define NONE -1
 
int main()
{
    int n;
    // 수열의 길이가 가장 작은 경우는 1이다.
    int biggerCount{ 1 }, smallerCount{ 1 };
    int preNumber{ NONE }, curNumber{ NONE };
 
    int longestCount{ 1 };
 
    // 수열의 길이를 입력받고 그 만큼 입력받으며 연속인지 확인한다.
    cin >> n;
    while (n)
    {
        cin >> curNumber;
 
        // 가장 처음 들어온 숫자는 무시한다.
        if (preNumber != NONE)
        {
            // 커지는 수열인지 확인
            if (curNumber >= preNumber)
            {
                biggerCount++;
            }
            else
            {
                // 현재 값이 이전 값보다 작아진 경우 가장 긴 길이를 갱신한다.
                if (biggerCount > longestCount)
                {
                    longestCount = biggerCount;
                }
                biggerCount = 1;
            }
            // 작아지는 수열인지 확인
            if (curNumber <= preNumber)
            {
                smallerCount++;
            }
            else
            {
                // 현재 값이 이전 값보다 커진 경우 가장 긴 길이를 갱신한다.
                if (smallerCount > longestCount)
                {
                    longestCount = smallerCount;
                }
                smallerCount = 1;
            }
        }
        preNumber = curNumber;
        n--;
    }
 
    // 마지막으로 확인한 뒤 가장 긴 길이를 출력한다.
    if (biggerCount > longestCount)
    {
        longestCount = biggerCount;
    }
    else if (smallerCount > longestCount)
    {
        longestCount = smallerCount;
    }
 
    cout << longestCount << endl;
}

JUNGOL) 문제은행) 실력키우기) 수열