[백준] 2491 수열

1. 문제

www.acmicpc.net/problem/2491

2491번: 수열

2. 접근방법

처음에 LIS 인 줄 알고 삽질하다가

틀렸습니다 5번 받고 다시 보니 아 그냥 배열 한번만 돌면 되는거구나 ..했다..

 

그냥 전 숫자보다 크거나 같으면서 연속된 갯수 세고

전숫자 보다 작거나 같으면서 연속된 갯수 세고

 

가장 많이 연속한 갯수만 출력하면 된다.

 

3. 자바 코드

package Silver;

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

public class P2491수열 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());

		int arr[] = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());

		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(st.nextToken());
		int maxleft = 1;
		int leftcnt = 1;
		int maxright = 1;
		int rightcnt = 1;
		for (int i = 1; i < N; i++) {
			if (arr[i - 1] <= arr[i]) {
				leftcnt++;
			} else {
				maxleft = Math.max(maxleft, leftcnt);
				leftcnt = 1;
			}
			if (arr[i - 1] >= arr[i]) {
				rightcnt++;
			} else {
				maxright = Math.max(maxright, rightcnt);
				rightcnt = 1;
			}
		}
		maxleft = Math.max(maxleft, leftcnt);
		maxright = Math.max(maxright, rightcnt);
		System.out.println(Math.max(maxright, maxleft));

	}
}

 

4. 마치며

LIS로 삽질하며 심지어 배열 크기 10만이길래 NlogN까지 찾아보고 있었는데 .. ㅜ