[백준 알고리즘] 백준 2491번 자바(Java) 수열

조건

문제

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 이하의 정수이다.

 

출력

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

 

풀이

이 문제는 반복문으로 수열안에 + - 여부를 판단하여 길이를 측정하는 간단한 문제라고 생각한다

그래서 간단하게 조건을 생각을 해보자면

1. 만일 수열의 수 i와 i-1이 동일하다면 same_len과 len 둘다 ++시켜준다2. len의 길이가 가장 긴길이보다 크다면 max_len = len 이 되도록 한다3. 혹여나 1244431 과 같은 예시가 나오면 44431이 수열이 되도록 4->3이 될때 len = same_len+1; 이 되도록 해준다

max_len = 5

max_len = 6

소스코드

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

public class Main {
	public static void main(String[] args)throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); //선언
	
		int N = Integer.parseInt(br.readLine());
		String line = br.readLine();
		StringTokenizer st = new StringTokenizer(line);
		int arr[] = new int[N];
		int plusminus = 0;
		int len = 1;
		int max_len = 1;	//가장 긴 길이
		int same_len = 1;	//같은 수가 얼마만큼 나오는지 체크
		
		for(int i = 0; i<N; i++)	//수열 저장
		{
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i = 1; i<N; i++)
		{
			if(arr[i] == arr[i-1])
			{
				len++;
				same_len++;
			}
			else if(arr[i] > arr[i-1]) //arr[i]가 전수보다 클경우
			{
				if(plusminus == 0)
				{
					plusminus = 1;
					len++;
				}
				else if(plusminus == 1)
				{
					len++;
				}
				else
				{
					plusminus = 1;
					len = (same_len + 1);
				}
				same_len = 1;
			}
			else	//arr[i]가 전수보다 작을 경우
			{
				if(plusminus == 0)
				{
					plusminus = -1;
					len++;
				}
				else if(plusminus == -1)
				{
					len++;
				}
				else
				{
					plusminus = -1;
					len = (same_len + 1);
				}
				same_len = 1;
			}
			if(len > max_len)
			{
				max_len = len;
			}
		}
		System.out.println(max_len);
	}

 

 

 

 

문제 출처

https://www.acmicpc.net/problem/2491

2491번: 수열