/ BOJ

BOJ_2491_수열_JAVA

문제 : 수열

링크 : BOJ_2491_수열

접근 방식

점점 작아지는 수열의 개수중 최댓값, 점점 커지는 수열의 개수중 최댓값 이 두 가지를 구한 다음에 구한 2개의 값을 또 비교하여 최댓값을 구하면 된다.

방법만 따졌을 때는, 시간복잡도가 O(N)으로 큰 시간은 아니다. 하지만 시간이 더 작게 주어진다면 이 문제의 카테고리가 동적 계획법인 만큼 동적 계획법으로 접근하는 게 좋지 않을까 싶다.

풀이 방법

  1. 작아지는 수열을 비교할 변수와 커지는 수열을 비교할 변수를 각각 선언한다.

  2. 먼저 점점 커지는 수열을 비교한다. 현재 수와 읽어온 다음 수를 비교하여 계속해서 크거나 같을 경우 카운트를 증가시킨다.

  3. 반복문이 도는 동안, 카운트의 최댓값을 계속해서 비교하여 카운트의 최댓값을 구한다.

  4. 2,3을 한 번 더 수행하는데, 2번째는 작아지는 경우를 비교한다.

  5. 커지는 경우의 MAX카운트와 작아지는 경우의 MAX카운트 2개를 비교해서 더 큰 값을 출력한다.

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ_2491_수열 {

	public static void main(String[] args) throws IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));


		int N = Integer.parseInt(in.readLine());

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");


		int cnt = 1;
		int max1 = 1;
		int first = Integer.parseInt(st.nextToken());
		int second = first;
		int[] arr = new int[N];
		for(int i=1;i<N;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		for(int i=1;i<N;i++) {
			int K = arr[i];

			if(K >= first) {
				cnt++;
				first = K;
			}else {
				cnt = 1;
				first = K;
			}
			max1 = Math.max(cnt, max1);
		}
		int cnt2 = 1;
		int max2 = 1;		
		for(int i=1;i<N;i++) {
			int K = arr[i];

			if(K <= second) {
				cnt2++;
				second = K;
			}else {
				cnt2 = 1;
				second = K;
			}
			max2 = Math.max(cnt2, max2);
		}
		System.out.println(Math.max(max1, max2));
	}

}