백준 2505번: 두 번 뒤집기

문제 링크

백준 2505번: 두 번 뒤집기

---

아이디어

보드를 뒤집는 구간을 [L1, R1], [L2, R2]라고 했을 때, 구간의 관계에 따라 3가지 경우가 존재한다.

두 구간이 독립적인 경우

두 구간이 서로 독립적인 경우이다. 이 경우는 브루트포스로 [L1, R1], [L2, R2]을 전부 구할 수 있으므로 문제가 되지 않는다.

---

한 구간이 다른 한 구간을 전부 포함하는 경우

한 구간이 다른 한 구간을 전부 포함하는 경우이다. 이 경우는 [L1, R1]을 찾아서 뒤집은 후, [L2, R2]를 찾아서 뒤집으면 된다. 브루트포스로 찾을 수 있으므로 역시 문제가 되지 않는다.

---

두 구간의 일부분이 겹치는 경우

문제는 두 구간의 일부분이 겹치는 경우이다. 앞의 두 경우는 구간을 찾기도 쉬웠고, 찾은 구간을 어떤 순서로 다시 뒤집든지 상관 없었다. 하지만 이 경우는 아니다. 구간을 찾기 어려운 건 둘째 치고 무조건 처음에 뒤집은 순서의 역순으로 다시 뒤집어야 한다.

L1, R1, L2, R2를 오름차순으로 정렬한 결과를 L1, L2, R1, R2라고 하자. [L1, R1]을 나중에 뒤집은 경우, board[R1] = L1이 성립한다. 반대로 [L2, R2]를 나중에 뒤집은 경우 board[L2] = R2가 성립한다.

이 두 가지 경우를 생각해서 [L1, R1], [L2, R2]를 찾고 두 번 뒤집어보면 답을 구할 수 있다. 당연하지만 첫 번째, 두 번째 케이스에도 이 방법이 유효하다.

시간복잡도는 $O(N)$이고, $N = 10000$에 시간 제한은 1초이므로 AC를 받을 수 있다.

---

코드

public class Main {
    public static void main(String[] args) throws IOException {
        Problem problem = new Problem();
        problem.init();
        problem.solve();
        problem.printAns();
    }
}


class Problem {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st;
    int N;
    int[] arr;
    int[] tmp;
    Queue<Integer> ans = new LinkedList<>();

    void init() throws IOException {
        N = Integer.parseInt(br.readLine());
        arr = new int[N + 1];
        tmp = new int[N + 1];

        st = new StringTokenizer(br.readLine());

        for(int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
    }

    void solve() {
        copyTmp();
        reverseL();
        reverseR();

        if(!isAnswer()) {
            ans = new LinkedList<>();
            copyTmp();
            reverseR();
            reverseL();
        }
    }

    void copyTmp() {
        for(int i = 1; i <= N; i++) {
            tmp[i] = arr[i];
        }
    }

    void reverseL() {
        int L = 1, R = 1;

        for(int i = 1; i <= N; i++) {
            if(tmp[i] != i) {
                L = i;
                break;
            }
        }

        for(int i = L + 1; i <= N; i++) {
            if(tmp[i] == L) {
                R = i;
                break;
            }
        }

        reverse(L, R);
        ans.add(L);
        ans.add(R);
    }

    void reverseR() {
        int L = N, R = N;

        for(int i = N; i >= 1; i--) {
            if(tmp[i] != i) {
                R = i;
                break;
            }
        }

        for(int i = R - 1; i >= 0; i--) {
            if(tmp[i] == R) {
                L = i;
                break;
            }
        }

        reverse(L, R);
        ans.add(L);
        ans.add(R);
    }

    void reverse(int L, int R) {
        for(int i = 0; i < (R - L + 1) / 2; i++) {
            int num = tmp[L + i];
            tmp[L + i] = tmp[R - i];
            tmp[R - i] = num;
        }
    }

    boolean isAnswer() {
        for(int i = 1; i <= N; i++) {
            if(tmp[i] != i) {
                return false;
            }
        }

        return true;
    }

    void printAns() throws IOException {
        bw.write(ans.poll() + " " + ans.poll() + "\n" + ans.poll() + " " + ans.poll());
        bw.flush();
        bw.close();
        br.close();
    }
}