백준 2505번 두 번 뒤집기 :: 마이구미

이 글은 백준 알고리즘 문제 2505번 "두 번 뒤집기" 를 풀이한다.

정올 출제 문제로써, 문제 이해를 통한 구현으로 해결할 수 있다.

문제 링크 - https://www.acmicpc.net/problem/2505

1부터 N까지의 숫자가 각 칸에 차례대로 들어있는 놀이판이 있다. 예를 들어 10 칸을 가진 놀이판의 초기 상태는 다음과 같다.  

1

2

3

4

5

6

7

8

9

10

구간[i,j]는 놀이판의 왼쪽 i번째 칸부터 j번째칸 사이에 있는 모든 숫자를 말한다. 단 구간[i,j]에서 항상  라고 가정한다. 우리는 이 놀이판의 한 구간을 잡아서 그 구간을 완전히 뒤집을  수 있다. 만일 초기상태에서 구간[3,8]을 뒤집으면 놀이판은 다음과 같이 변한다.

1

2

8

7

6

5

4

3

9

10

이어 이 상태에서 구간[1,5]를 다시 뒤집으면 놀이판은 다음과 같이 바뀐다. 

6

7

8

2

1

5

4

3

9

10

여러분은 두 번 뒤집힌 놀이판의 상태를 입력으로 받아서 이를 다시 초기 상태로 돌리기 위해서 어떤 두 구간을 차례대로 뒤집어야 하는지를 계산해야 한다. 즉 여러분이 찾아낸 두 개의 구간대로 입력 놀이판을 차례대로 뒤집으면, 놀이판은 초기상태인 1, 2, 3, ...., N 으로 되돌아가야 한다.  

단 어떤 경우에는 초기상태로 되돌릴 수 있는 두 구간이 여러 개 있을 수도 있는데, 그러한 경우에는 그 중 하나만 출력해도 된다. 구간[i,i]를 뒤집으면 아무런 변화가 없는데 이러한 것도 허용이 된다.

본인은 항상 문제를 제대로 읽고 풀겠다는 다짐을 해도 잘 지켜지지 않는다. 

그로인해, 이 문제를 엄청 헤맸다.

이 문제는 다시 한번 문제를 꼼꼼하게 읽고, 이해해야하는 것을 상기시켜준다.

문제의 중점은 다음과 같다.

1 ~ N 까지 순차적으로 되돌아가기 위한 구간을 찾는다.

문제의 이름은 "두 번 뒤집기", 말 그대로 2번이다. 

즉, 무조건 2번을 뒤집는다.

예를 들어, 다음과 같이 주어졌을 경우를 보자.

0번, 1번, 2번 뒤집는 경우가 존재한다. (답은 항상 존재한다고 명시했기에, 3번 이상 뒤집는 경우는 없다.)

1 2 3 4 5
=> 1 1
=> 1 1

1 2 3 5 4
=> 1 1
=> 4 5

문제 설명을 보다시피 아무런 변화가 없는 것도 허용했다.

그로인해, 무조건 답은 두 구간을 출력해주어야한다.

이 부분에서 많이 틀렸을 것이라 생각한다.

문제를 이해했다면, 이제 어떻게 뒤집는 구간을 찾을 것인가?

항상 답이 존재하는 경우만 주기 때문에, 간단하게 생각할 수 있다.

1 ~ N 까지 순차적이기에, 각 배열의 인덱스의 값은 인덱스와 동일한 값이 온다는 것을 알 수 있다.

1 ~ N 의 값이 배열의 어느 인덱스에 위치하는 지 찾은 후, 뒤집어주면 된다.

그림을 통해 표현하면 다음과 같다.

위와 같이 순차적으로 찾아 뒤집는 경우와 함께 역순으로 찾아 뒤집는 경우도 고려해야한다.

Github - https://github.com/hotehrud/acmicpc/blob/master/KOI/2008/2505.java

static StringBuilder sb1 = new StringBuilder();
static StringBuilder sb2 = new StringBuilder();
private void solve() {
    int[] array = new int[10001];
    int n = sc.nextInt();
 
    for (int i = 1; i <= n; i++) {
        array[i] = sc.nextInt();
    }
 
    if (front(array, 1, n)) {
        return;
    } 
    back(array, n, 1);
}
 
public static boolean front(int[] origin, int target, int n) {
    int[] array = origin.clone();
    int cnt = 0;
    while (target != n) {
        for (int i = target; i <= n; i++) {
            if (target == array[target]) {
                break;
            }
            if (array[i] == target) {
                cnt++;
                reverse(array, target, i);
                sb1.append(target + " " + i + "\n");
            }
        }
        target++;
    }
 
    if (cnt == 1) {
        System.out.println("1 1");
        System.out.println(sb1.toString());
        return true;
    } else if (cnt == 2) {
        System.out.println(sb1.toString());
        return true;
    } else {
        return false;
    }
}
 
public static boolean back(int[] origin, int target, int n) {
    int[] array = origin.clone();
    int cnt = 0;
    while (target != n) {
        for (int i = target; i >= n; i--) {
            if (target == array[target]) {
                break;
            }
            if (array[i] == target) {
                cnt++;
                reverse(array, i, target);
                sb2.append(i + " " + target + "\n");
            }
        }
        target--;
    }
 
    if (cnt == 1) {
        System.out.println("1 1");
        System.out.println(sb2.toString());
        return true;
    } else if (cnt == 2) {
        System.out.println(sb2.toString());
        return true;
    } else {
        System.out.println("1 1");
        System.out.println("1 1");
        return false;
    }
}
 
public static void reverse(int[] array, int s, int e) {
    int n = (int) Math.ceil((e - s) / 2.0);
    for (int i = 0; i < n; i++) {
        int temp = array[s + i];
        array[s + i] = array[e - i];
        array[e - i] = temp;
    }
}