[BOJ] 백준 2505 두 번 뒤집기

출처: https://www.acmicpc.net/problem/2505

 Input 

10

6 7 8 2 1 5 4 3 9 10

 

 Output 

1 5

3 8

초기에 1...N 까지 정상 문자열을 두 번 뒤집어서 Input Data로 주어지는 것이기 때문에　

무조건 답인 두 구간을 출력해야 합니다.

- 앞쪽에서부터 뒤집기 2번 내로 성공할 수 있는지 확인

- 뒤쪽에서부터 뒤집기 2번 내로 성공할 수 있는지 확인

뒤집기(Reverse()) 연산을 사용해야 하는 시점은 다음과 같습니다.

배열 인덱스에 맞는 값이 오지 않았을 때입니다.

array[i] ?= i 이를 앞쪽과 뒷쪽 각각 수행합니다.

 

 

# 뒤집기 1번 필요한 경우

 Input 

10

1 2 3 6 5 4 7 8 9 10

 

 Output 

4 6

1 1

 

# 뒤집기 0번 필요한 경우

 Input 

10

1 2 3 4 5 6 7 8 9 10

 

 Output 

1 1

1 1

---

import java.io.*;
import java.util.*;
 
public class Main {
    static int[] origin, array;
    static int N;
    static Interval first, second;
     
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
         
        N = sc.nextInt();
        origin = new int[N + 1];
         
        for (int i = 1; i <= N; i++) {
            origin[i] = sc.nextInt();
        }
     
        first = new Interval();
        second = new Interval();
         
        // 앞에서 부터 진행한 탐색에서 종료 여부
        if(!front()) {
            first.reset(); second.reset();
            // front()에서 성공하지 못했다면 back에서는 무조건 성공 보장
            back();
        }
         
        System.out.println(first.x + " " + first.y);
        System.out.println(second.x + " " + second.y);
             
    }
 
    private static boolean front() {
        array = origin.clone();
        int reverseCnt = 0;
         
        for(int i=1; i<=N; i++) {
            if(array[i] != i) {
                int s = i;
                 
                int e = N;
                for(int j=i+1; j<=N; j++) {
                    if(array[j] == i) {
                        e = j;
                        break;
                    }
                }
                reverse(s, e);
                reverseCnt++;
                if(reverseCnt == 1) {
                    first.x = s; first.y = e;
                }
                else if(reverseCnt == 2) {
                    second.x = s;
                    second.y = e;
                }
            }
            if(reverseCnt >= 3) break;
        }
        // 뒤집기가 두 번이내로 탐색이 끝난 경우
        if(reverseCnt <= 2) return true;
        return false;
    }
     
    private static boolean back() {
        array = origin.clone();
        int reverseCnt = 0;
         
        for(int i=N; i>=1; i--) {
            if(array[i] != i) {
                int s = 1;
                int e = i;
                for(int j=1; j<e; j++) {
                    if(array[j] == i) {
                        s = j;
                        break;  
                    }
                }
                reverse(s, e);
                reverseCnt++;
                if(reverseCnt == 1) {
                    first.x = s; first.y = e;
                }
                else if(reverseCnt == 2) {
                    second.x = s;
                    second.y = e;
                }
            }
            if(reverseCnt >= 3) break;
        }
        // 정확히 두 번만에 탐색이 끝난 경우
        if(reverseCnt <= 2) return true;
        return false;
    }
     
 
    private static void reverse(int start, int end) {
        while(start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++; end--;
        }
    }
}
 
class Interval{
    int x, y;
     
    public Interval() {
        x = 1;
        y = 1;
    }
 
    public void reset() {
        x = 1;
        y = 1;
    }
}