백준 20127 자바 - Y-수열 (BOJ 20127 JAVA)

문제 : boj20127

 

 

  증가수열 또는 감소수열인 것은 해결 로직을 세우는데에 상관이 없다. 증가수열, 감소수열 둘다 별도 로직으로 계산한다고 생각하면 그 중 작은걸 출력하면 된다. 기본적으론 이런데, 이 문제의 경우 정답률이 낮은만큼 많은 경우를 세세하게 예외처리해줘야 통과할 수 있다. 이하 여러가지 케이스에 대해 설명해본다.

 

 

1. 

  기본 로직은 증가수열을 체크한다면 수가 작아지는 부분을, 감소수열을 체크한다면 수가 커지는 부분의 개수가 2개 이상이라면 증가 혹은 감소수열이 될 수 없다. 예를들어 '예제 입력 1'에 대해 증가수열로써 체크한다면 감소하는 경우가 1번 이하이므로 가능하다! 하지만 감소수열로써 체크한다면 감소하는 경우가 2번 이상이므로 감소수열로는 만들 수 없다.

 

2.

  이번엔 '1'와 같은 경우인데 한가지 더 체크해야 할 점을 확인해보자. '3 4 5 1 2'와 '3 4 5 1 4'에 대해 증가하는 수열을 체크하는 중이다. 둘 다 감소하는 경우가 1번 이하이므로 가능할 것 같지만, 실제로 뒤로 옮겨보면 후자의 경우는 성립하지 않는다.

  따라서 증가하는 수열로 보자면 감소하는 경우가 1번일 경우 수열의 맨 처음값이 수열의 맨 뒷값보다 크거나 같아야 성립함을 알 수 있다. 마찬가지로 감소하는 수열로 체크한다면 증가하는 경우가 1번일 경우엔 수열의 맨 처음값이 맨 뒷값보다 작거나 같아야 성립한다.

 

  참고로 k는 증가하는 수열로 보고 있는 경우 처음 감소된 위치의 index, 감소하는 수열로 보고 있는 경우 마찬가지로 처음 증가된 위치의 index가 된다. 예를들어 위의 '3 4 5 1 2' 경우 index가 2->3으로 가면서 감소하였으므로 k=3이다.

 

 

3.

  이건 당연한건데, '1 5 2 4 3 6' 이런식으로 증가와 감소 모두 감소하거나 증가하는 부분이 2개가 넘는다면 -1을 출력해주고 끝내면 된다.

 

 

4.

  모든 수가 같은 경우 (e.g. '1 1 1 1 1')와, 모든 수가 증가하는 경우(e.g. '1 2 3 4 4'), 혹은 모든 수가 감소하는 경우 (e.g. '5 4 3 2 1') 0을 출력하면 된다.

 

 

5.

  '5 1 5 5 5'와 같은 경우를 보자. 이 경우 증가체크, 감소체크 둘 다 성립된다. 하지만 증가하는 수열로 체크시엔 k가 1이 되고, 감소로 체크시엔 k=2가 되므로 '가능한 k가 여러 개면 가능한 가장 작은 k를 출력' 조건에 따라 1을 출력해줘야 한다.

 

  세세하게 모두 체크해야해서 생각을 다 했다고 해도 구현은 상당히 어려울 수 있는 문제이다. 또한 별다른 알고리즘 지식 없이 이 문제에 맞는 로직을 찾아야 하는 '애드혹(ad-hoc)' 문제이다. 아무튼 위의 경우 전부 체크 가능하도록 짜면 AC 가능!

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        
        int inc = 0;
        int dec = 0;
        boolean isInc = true;
        boolean isDec = true;
        int[] arr = new int[n];
        arr[0] = nextInt();
        for (int i = 1; i < n; i++) {
            arr[i] = nextInt();
            if (isInc && arr[i] < arr[i-1]) {
                if (inc == 0) inc = i;
                else isInc = false;
            }
            if (isDec && arr[i] > arr[i-1]) {
                if (dec == 0) dec = i;
                else isDec = false;
            }
            if (!isDec && !isInc) {
                System.out.println(-1);
                return;
            }
        }

        if (isDec && isInc ) {
            if (inc == 0 && dec == 0) { // all same
                System.out.println(0);
            } else {
                System.out.println(Math.min(inc, dec)); //e.g. 5 4 5 5 5
            }
            return;
        }

        if (isInc && (inc == 0 || arr[0] >= arr[n-1])) {
            System.out.println(inc);
            return;
        }
        if (isDec && (dec == 0 || arr[0] <= arr[n-1])) {
            System.out.println(dec);
            return;
        }
        System.out.println(-1);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}