[ BOJ 2478 ] 자물쇠

플래티넘!💎

진짜 어려웠다....
몇ㅎ시간 붙잡고 있어도 안풀려서 다른 분들의 풀이를 참고했지만,,,,,
계속되는 실패!!!

그래서 그냥 우선 모든 경우의 수를 처리해보는 방식으로 구현했다,..... 처음에 이거 무족권 시간초과라고 생각했는데
어라...? 통과!@!!!@!@!@!@! 나익수!!!

풀이

주어진 N개의 숫자는 1,2,3,4,...., N 을

1. 왼쪽으로 k1번 밀기
2. p~q 구간 뒤집기
3. 왼쪽으로 k2번 밀기

과정으로 만들어진 것이다.

그래서 이것을 반대로!! 진행
여기서 가장 중요한 것은 1 <= k1, k2 < N
무조권 1번은 옮겨야하고, N번 이동시켜서 원래 위치 그대로 이동하는 것은 안됨!!!

그래서

1. 1 ~ N번 동안 반대로 오른쪽으로 이동시키면서 앞 뒤 차이가 1 or N-1 이 아닌 구간을 찾는다.
   • 이 찾은 겂들을 모두 저장! -> candidates
   • 중요한 것은 구간 위치(p, q)와 이동시킨 횟수(k2)를 함께 저장
2. candidates를 모두 돌면서 (p, q) 부분을 뒤집은 후에 1~N-1번의 이동으로 원래 순서 1,2,3,....,N 이 가능한지를 체크하면 끝!!

그런데 여기서 중요한 것은
N = 8 일때,

• 8 7 6 5 4 3 2 1 처럼 전체가 역순으로 뒤집힌 경우
• 7 6 5 4 3 2 1 8 처럼 1 ~ N-1 구간이 뒤집힌 경우
• 1 8 7 6 5 4 3 2 처럼 2 ~ N 구간이 뒤집힌 경우
  이다.
  이러한 경우에는 처음에 candidates가 하나도 나오지 않는다....

그래서 이러한 경우에는 따로 예외처리를 해줘야한다.

이미 위의 코드에서 N-1번 오른쪽으로 이동된 상태!
즉, 8 7 6 5 4 3 2 1 -> 7 6 5 4 3 2 1 8 == 왼쪽으로 1번 이동한 상태!

이 상태에서 다시 1번 ~ N-1번을 오른쪽으로 이동시키면서
8 7 6 5 4 3 2 1 순으로 정렬되는 타임을 찾으면 끝!!
이 경우에는 k1 = 1; (p, q) = (1, N); k2 = time; 이 된다!

예시로 코드를 확인!
N = 10 9 2 1 10 3 4 5 6 7 8
candidates = {{3,5,1},{4,6,2},{5,7,3},{6,8,4},{7,9,5},{2,8,7},{3,9,8}}

1) {p,q,t} = {3,5,1}
1. 오른쪽으로 t번 이동 = 8 9 2 1 10 3 4 5 6 7
2. (p, q) 뒤집기 = 8 9 10 1 2 3 4 5 6 7
3. 1 ~ N-1번 이동하면서 순서대로 오는지 확인
1. 7 8 9 10 1 2 3 4 5 6
2. 6 7 8 9 10 1 2 3 4 5
3. 5 6 7 8 9 10 1 2 3 4
4. 4 5 6 7 8 9 10 1 2 3
5. 3 4 5 6 7 8 9 10 1 2
6. 2 3 4 5 6 7 8 9 10 1
7. 1 2 3 4 5 6 7 8 9 10
-> 7번 이동으로 원래 순서대로 만듬!!
4. 즉, 1 2 3 4 5 6 7 8 9 10 을 k1 = 7번 왼쪽으로 이동시키고, (3, 5) 부분을 뒤집고, k2 = 1번 이동시키면
=> 9 2 1 10 3 4 5 6 7 8 이 나옴!!!

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.*;
import java.util.stream.Collectors;

public class Main_BOJ_2478_자물쇠 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        List<Integer> q = new ArrayList<>();

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            q.add(arr[i]);
        }

        List<int[]> candidates = new ArrayList<>();

        for (int i = 1; i < N; i++) {
            q.add(0, q.get(q.size() - 1));
            q.remove(q.size() - 1);
            List<Integer> tmp = new ArrayList<>();

            for (int j = 1; j < N; j++) {
                int t = Math.abs(q.get(j) - q.get(j - 1));
                if (t != 1 && t != N - 1) tmp.add(j);
            }

            if (tmp.size() == 2) candidates.add(new int[]{tmp.get(0) + 1, tmp.get(1), i});
        }

        int time = -1;
        for (int[] candidate : candidates) {
            q = Arrays.stream(arr).boxed().collect(Collectors.toList());

            for (int t = 0; t < candidate[2]; t++) {
                q.add(0, q.get(q.size() - 1));
                q.remove(q.size() - 1);
            }

            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < candidate[0] - 1; i++) {
                tmp.add(q.get(i));
            }
            for (int i = candidate[1] - 1; i >= candidate[0] - 1; i--) {
                tmp.add(q.get(i));
            }
            for (int i = candidate[1]; i < N; i++) {
                tmp.add(q.get(i));
            }

            time = -1;
            for (int i = 0; i < N - 1; i++) {
                tmp.add(0, tmp.get(tmp.size() - 1));
                tmp.remove(tmp.size() - 1);

                if (tmp.get(0) == 1 && tmp.get(tmp.size() - 1) == N) {
                    time = i + 1;
                    break;
                }
            }

            if (time > 0) {
                System.out.println(time);
                System.out.println(candidate[0] + " " + candidate[1]);
                System.out.println(candidate[2]);
                break;
            }
        }

        if (time == -1) {
            for (int i = 1; i < N; i++) {
                q.add(0, q.get(q.size() - 1));
                q.remove(q.size() - 1);

                if (q.get(0) == N && q.get(q.size() - 1) == 1) {
                    time = i;
                }
            }
            System.out.println(1);
            System.out.println("1 " + N);
            System.out.println(time);
        }
    }
}