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

 

20127번: Y-수열

N개의 정수로 이루어진 수열 a1, ... , aN이 있다. 택희는 해당 수열이 증가수열 혹은 감소수열이 되게 만들고 싶다. 증가수열은 모든 i(1 ≤ i < N)에 대해서 ai ≤ ai+1을 만족하는 수열이고, 감소수열

www.acmicpc.net

 

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

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

 

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

 

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

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

 

증가수열을 만들 때는

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

감소수열을 만들 때는

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

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

 

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

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
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();
    }
}
cs

'algorithm > Implementation' 카테고리의 다른 글

boj 16918 봄버맨  (0) 2021.02.17
boj 16935 배열 돌리기 3  (0) 2021.02.10
boj 1914 하노이 탑  (0) 2021.02.07
boj 11729 하노이 탑 이동 순서  (0) 2021.02.07
boj 1244 스위치 켜고 끄기  (0) 2021.02.01

+ Recent posts

티스토리툴바