🙏 23. 연속 부분 증가수열

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비 - 인프런 | 강의

모든 문제에 대한 저작권은 위 강의에 있습니다.

문제

N개의 숫자가 나열된 수열이 주어집니다. 이 수열 중 연속적으로 증가하는 부분 수열을 최대 길이를 구하여 출력하는 프로그램을 작성하세요. 만약 N=9이고 5 7 3 3 12 12 13 10 11 이면 “3 3 12 12 13”부분이 최대 길이 증가수열이므로 그 길이인 5을 출력합니다. 값이 같을 때는 증가하는 걸로 생각합니다.

입력 설명

첫 줄에 자연수의 개수 N(5<=N<=100,000)이 주어집니다. 두 번째 줄에 N개의 숫자열이 주어집니다. 각 숫자는 100,000이하의 자연수입니다.

출력 설명

최대 부분 증가수열의 길이를 출력하세요.

입력 예제 1

9
5 7 3 3 12 12 13 10 11

출력 예제 1

5

제출 코드

2023년 2월 10일

#include <iostream>
#include <vector>

using namespace std;

int Check(vector<int> numbers)
{
		int count = 0;
		int maxCount = 0;
		int prevNum = 0;
		int length = numbers.size();
	
		for (int i = 0; i < length; i++)
		{
				if (numbers[i] >= prevNum)
				{
						count++;
						if (count > maxCount)
								maxCount = count;
				}
				else
						count = 1;
		
				prevNum = numbers[i];
		}
	
		return maxCount;
}

int main()
{
		int N = 0;
		cin >> N;
		vector<int> numbers;
	
		for (int i = 0; i < N; i++)
		{
				int temp = 0;
				cin >> temp;
		
				numbers.push_back(temp);
		}
	
		cout << Check(numbers);
	
		return 0;
}

풀이

현재 비교하는 요소와 이전 요소를 비교하여 같거나 크면 횟수를 카운트해주었다.