[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이하의 자연수입니다.

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

💡 입력예제
9
5 7 3 3 12 12 13 10 11

💡 출력예제
5

 

---

코드

최종 풀이

#include <stdio.h>
#include <vector>

int main() {
	int n, i, cnt = 0, tmp, max = 0;
	scanf("%d", &n);
	std::vector<int> arr(n);
	for(i = 0; i < n; i++) {
		scanf("%d", &arr[i]);
	}
	tmp = arr[0];
	for(i = 0; i < n; i++) {
		if(arr[i] >= tmp) {
			tmp = arr[i];
			cnt++;
			if(cnt > max) {
				max = cnt;
			}
		}
		else if(arr[i] < tmp) {
			tmp = arr[i];
			cnt = 1;
		}
	}
	
	printf("%d ", max);
	return 0;
}

 

---

설명

사용자로부터 수열의 개수 N을 입력받는다.

N번 반복하는 for문을 작성하여 수열을 입력받아 arr에 할당한다.

첫번째 입력 받은 숫자를 tmp에 할당해놓고 해당 숫자가 현재 수열보다 클 경우와 작은 경우를 counting하기 위해 N번 반복하는 for문을 작성한다.

현재 수열이 전 숫자보다 크거나 같을 경우 cnt를 1씩 증가하고 현재 수열을 tmp로 할당시켜놓는다. 만약 cnt가 max보다 클 경우 max에 cnt를 할당해놓는다.

만약 현재 수열이 전 숫자보다 작을 경우 cnt를 1로 초기화 하고 tmp를 현재 수열로 갱신한다.

최종적으로 for문을 빠져나오면 max를 출력하여 마무리한다. 

 

---

 

해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.