boj 20127 Y-수열

 

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

20127번: Y-수열

 

맨 앞의 k개의 원소를 맨 뒤로 옮겨서 증가 또는 감소수열을 만들어야하는데 여기서 k의 최솟값을 출력해야합니다.

반례로 만들 수 없다면 -1을 출력합니다.

 

우선 맨 앞의 연속된 k개의 원소를 한 번만 움직이는거기 때문에 주어진 배열 list를 구간별로 나누면 2개의 구간이 나옵니다.

 

(편의를 위해 앞에서부터 구간1, 구간2로 하겠습니다.)

구간1의 맨 앞의 숫자가 구간2의 뒤로 가기때문에

 

증가수열을 만들 때는

구간1의 맨 앞의 숫자가 구간2의 맨 뒤의 숫자보다 크거나 같아야하고,

감소수열을 만들 때는

구간1의 맨 앞의 숫자가 구간2의 맨 뒤의 숫자보다 작거나 같아야합니다.

증가, 감소 수열을 만들 때 나온 각각의 k를 비교하여 작은 수를 출력하면 됩니다.

 

예외처리로 구간이 1개 나온다면 그냥 증가 또는 감소수열이 주어진 것이므로 0을 출력하면 되고,

2개보다 많이 나온다면 만들 수 없는 것이므로 -1입니다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static Queue<ArrayList<Integer>> inq = new LinkedList<>();
    static Queue<ArrayList<Integer>> deq = new LinkedList<>();
    static int N, inans, deans;
    static int list[] = new int[1000001];
 
    static void func() {
        ArrayList<Integer> newlist = new ArrayList<>();
        newlist.add(list[0]);
        for (int i = 1; i < N; i++) {
            if (list[i] >= list[i - 1])
                newlist.add(list[i]);
            else {
                inq.add(newlist);
                newlist = new ArrayList<>();
                newlist.add(list[i]);
            }
        }
        inq.add(newlist);
        if (inq.size() > 2)
            inans = -1;
        else if (inq.size() == 1)
            inans = 0;
        else {
            int size = inq.peek().size();
            int l = inq.peek().get(0);
            inq.remove();
            int r = inq.peek().get(inq.peek().size() - 1);
 
            if (l >= r)
                inans = size;
            else
                inans = -1;
        }
 
        newlist = new ArrayList<>();
        newlist.add(list[0]);
        for (int i = 1; i < N; i++) {
            if (list[i] <= list[i - 1])
                newlist.add(list[i]);
            else {
                deq.add(newlist);
                newlist = new ArrayList<>();
                newlist.add(list[i]);
            }
        }
        deq.add(newlist);
 
        if (deq.size() > 2)
            deans = -1;
        else if (deq.size() == 1)
            deans = 0;
        else {
            int size = deq.peek().size();
            int l = deq.peek().get(0);
            deq.remove();
            int r = deq.peek().get(deq.peek().size() - 1);
 
            if (r >= l)
                deans = size;
            else
                deans = -1;
        }
    }
 
    static void solve() {
        if (inans == -1 && deans == -1)
            System.out.println(-1);
        else if (inans == -1)
            System.out.println(deans);
        else if (deans == -1)
            System.out.println(inans);
        else
            System.out.println(Math.min(inans, deans));
    }
 
    static void input() throws Exception {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            list[i] = Integer.parseInt(st.nextToken());
        }
    }
 
    public static void main(String[] args) throws Exception {
        input();
        func();
        solve();
    }
}