[백준] JAVA - 2491.수열

생각

증가하는 수열 또는 감소하는 수열 중 가잔 긴 부분의 길이를 구하는 문제입니다. 증가하는 수열과 감소하는 수열 두가지로 나누어 풀었습니다. N이 최대 100,000 이기 때문에 반복문을 중복해서 쓰지 않고, 직전값과 현재 값을 비교하기 위해 Stack 자료구조를 사용했습니다.

 

증가하는 수열에서 가장 긴 부분을 찾을때

 

1. 스택이 비어있으면 값을 넣어줍니다.

2. 스택이 비어있지 않다면 스택의 peek 값과 현재 값을 비교하여 현재 값이 더 크다면 스택에 넣어줍니다.

3. 스택이 비어있지 않고 스택의 peek 값 > 현재값 이라면 현재까지 쌓인 스택의 길이를 확인하여 maxLength에 갱신해줍니다. 그 다음 스택을 비워준다음 현재값을 다시 넣습니다.

4. 반복문을 모두 돈다음 스택의 길이를 maxLength와 비교하여 최대값을 찾아줍니다.

 

감소하는 수열도 위와 동일한 로직으로 구현했습니다.

Java code

package com.java.algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
/**
 * 연속적으로 증가하거나 감소하는 최장길이
 * 
 * */
public class Baekjoon_2491_수열 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		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());
		}
		Stack<Integer> plus = new Stack<Integer>();
		Stack<Integer> minus = new Stack<Integer>();
		//증가 찾기
		int maxLength = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			if(plus.isEmpty()) {
				plus.add(arr[i]);
			}else {
				if(plus.peek() <= arr[i]) {
					plus.add(arr[i]);
				}else {
					maxLength = Math.max(maxLength, plus.size());
					plus.clear();
					plus.add(arr[i]);
				}
			}
		}
		maxLength = Math.max(maxLength, plus.size());
		
		//감소 찾기
		int minLength = Integer.MIN_VALUE;
		for (int i = 0; i < N; i++) {
			if(minus.isEmpty()) {
				minus.add(arr[i]);
			}else {
				if(minus.peek() >= arr[i]) {
					minus.add(arr[i]);
				}else {
					minLength = Math.max(minLength, minus.size());
					minus.clear();
					minus.add(arr[i]);
				}
			}
		}
		minLength = Math.max(minLength, minus.size());
		
		int ans = Math.max(maxLength, minLength);
		System.out.println(ans);
	}
	
}