백준 20127 <Y-수열>

이 문제는 어떻게 흐름을 파악하고 문제에서 말하는 것이 무엇인가! 하는 문제이다.

 

이 문제의 핵심은 앞에 있는 수열을 뒤로 옮겨서 증가, 또는 감소가 되는지이다.

 

즉 앞에 있는 수열을 최대 한번! 이동하는 것이다.

 

이 문제를 생각해보면 n^2 해서도 풀 수 있지만 그렇게 된다면 100만의 제곱! 시간 초과이다.

 

즉 n번의 탐색으로 증가가 되는지, 또 n번 돌려서 감소가 되는지를 찾는 문제이다.

 

문제 풀이

1. 증가수열 먼저 --> 탐색하면서 감소하는 구간 있으면 count를 증가 현재까지의 증가수열 개수를 저장
2. count가 1 넘으면 한 번만으로 안됨 return 
3. 1번이면 맨 처음 수와 맨 마지막 비교해서 맨 처음수가 맨 마지막보다 작으면 증가수열 개수를 result로, 0 이면 result=0
4. 감소 수열 --> 탐색하면서 증가하는 구간 있으면 count를 증가 현재까지의 감소 수열 개수를 저장
5. count가 1 넘으면 한 번만으로 안됨 return 
6. 1번이면 맨 처음 수와 맨 마지막 비교해서 맨 처음수가 맨 마지막보다 크면 증가수열 개수를 result로, 0 이면 result=0

이 부분은 증가 수열이지만 반대로 감소 수열도 마찬가지이다. 이 두 개의 result값을 비교해서 작은 값을 출력하고 안되면 -1을 출력한다.

 

이 문제는 생각하는 문제로서 적당한 문제 같다!!

 

전체 코드

import java.awt.Point;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {


	static int n,num[],result=Integer.MAX_VALUE;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n=Integer.parseInt(br.readLine());
		num=new int[n];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			num[i]=Integer.parseInt(st.nextToken());
		}
		up();
		down();
		if(result==Integer.MAX_VALUE) {
			System.out.println("-1");
		}
		else {
			System.out.println(result);
		}

	}

	private static void down() {
		// TODO Auto-generated method stub
		int count=0;
		Queue<Integer> q=new LinkedList<Integer>();
		int change=1;
		for(int i=1;i<n;i++) {
			if(num[i-1]<num[i]) {
				count++;
				q.add(change);
				change=1;
			}
			else {
				change++;
			}
		}
		if(count>1) {
			return;
		}
		else if(count==1) {
			if(num[0]<=num[n-1]) {
				result=Math.min(result,q.remove());
			}
		}
		else {
			result=0;
		}
	}

	private static void up() {
		// TODO Auto-generated method stub
		int count=0;
		Queue<Integer> q=new LinkedList<Integer>();
		int change=1;
		for(int i=1;i<n;i++) {
			if(num[i-1]>num[i]) {
				count++;
				q.add(change);
				change=1;
			}
			else {
				change++;
			}
		}
		if(count>1) {
			return;
		}
		else if(count==1) {
			if(num[0]>=num[n-1]) {
				result=Math.min(result,q.remove());
			}
		}
		else {
			result=0;
		}
	}

	

	
}