[Java] 백준알고리즘 #10811 바구니 뒤집기

백준알고리즘 #10811 바구니 뒤집기

 

이전에 풀어보았던 바구니안에 공 넣기와 공 바꾸기와 유사한 문제이다.

 

2023.09.29 - [Java/백준알고리즘] - [Java] 백준알고리즘 #10810 공 넣기

[Java] 백준알고리즘 #10810 공 넣기

2023.09.29 - [Java/백준알고리즘] - [Java] 백준알고리즘 #10813 공 바꾸기

[Java] 백준알고리즘 #10813 공 바꾸기

 

다만 역순으로 배치하는 것이 조금 까다로운데, 먼저 전체 코드를 보자.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] basket = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            basket[i] = i;
        }
        for (int x = 0; x < m; x++) {
            int i = sc.nextInt();
            int j = sc.nextInt();
            for (int y = 0; y < (j - i) / 2 + 1; y++) {
                int tmp = basket[i + y];
                basket[i + y] = basket[j - y];
                basket[j - y] = tmp;
            }
        }
        for (int i = 1; i <= n; i++) {
            System.out.print(basket[i] + " ");
        }

        sc.close();
    }
}

바구니의 번호가 헷갈려 n + 1 의 크기의 배열을 만들었다. (인덱스와 바구니 번호를 일치시키기 위해)

바구니가 n개 있고, 그 중 i부터 j까지를 역순으로 바꾼다고 하면 다음과 같은 과정을 거친다.

n[i] 와 n[j]를 바꾼다.

n[i+1]과 n[j+1]을 바꾼다.

...

n[i+x]와 n[j-x]을 바꾼다. (이때, n[i+x] <= n[j-x])

 

이 과정에 수를 대입해보면

 

1번부터 5번까지 바꾼다고 하면 (홀수개)

1번과 5번의 위치를 바꾼다

2번과 4번의 위치를 바꾼다

3번과 3번의 위치를 바꾼다(혹은 그대로 둔다)

 

2번부터 5번까지의 위치를 바꾼다고 하면 (짝수개)

2번과 5번의 위치를 바꾼다.

3번과 4번의 위치를 바꾼다.

 

홀수개와 짝수개의 위치를 바꿀 때 시행하는 횟수가 일치하도록 반복문의 범위를 조절한다.

for (int y = 0; y < (j - i) / 2 + 1; y++)

1번부터 5번까지인 경우

(5-1) / 2 + 1 = 3

이 되어 3회 반복 실시.

 

2번부터 5번까지인 경우

(5-2) / 2 + 1 = 2.5 (int형이므로 2가 됨)

가 되어 2회 반복 실시.

 

이제 반복횟수를 구했으므로, 위치를 바꿔주는 알고리즘을 반복한다면 완성.

for (int y = 0; y < (j - i) / 2 + 1; y++) {
    int tmp = basket[i + y];
    basket[i + y] = basket[j - y];
    basket[j - y] = tmp;
}