백준 10811 - 바구니 뒤집기

문제 이름 : 바구니 뒤집기

---

문제

도현이는 바구니를 총 N 개 가지고 있고,

각각의 바구니에는 1 번부터 N 번까지 번호가 순서대로 적혀져 있다.

바구니는 일렬로 놓여져 있고,

가장 왼쪽 바구니를 1 번째, 2 번째, .. 가장 오른쪽 바구니를 N 번째 바구니라고 부른다.

입력

첫째 줄에 N ( 1 <= N <= 100 ) 과 M ( 1 <= M <= 100 ) 이 주어진다.

둘째 줄부터 M 개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다.

방법은 i, j 로 나타내고,

왼쪽 i 번째 바구니부터 j 번째 바구니의 순서를 역순으로 만든다는 뜻이다.

( 1 <= i <= j <= N )

도현이는 입력으로 주어진 순서대로 바구니의 순서를 바꾼다.

출력

모든 순서를 바꾼 후에,

가장 왼쪽의 바구니부터 순서대로 공백으로 구분하여 출력한다.

예제 입력 1

5 4
1 2
3 4
1 4
2 2

예제 출력 1

3 4 1 2 5

---

이 문제는 간단한 시뮬레이션 문제이지만,

바로 풀기에는 실제로 머리 속, 혹은 직접 어떤 상황인지를 구현 해 본 후 작성하는 것이 좋다.

일단, 문제에 대한 이해를 하고 시뮬레이션 해 보자 :

각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.

정수형 배열이 필요하며, 배열의 길이는 N 이다.

배열의 각 요소는 실제 인덱스 + 1 을 포함하고 있다. Ex - arr[0] = 1

따라서, 배열의 생성과 동시에 반복문으로 내용물을 채워넣어줘야 한다.

앞으로 M 번 바구니의 순서를 역순으로 만들려고 한다.

반복 계산해야 할 수는 M 번이라는 의미.

M 개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어지며, 이는 i, j 로 나타낸다.

i 번째 바구니부터, j 번째까지의 바구니 순서를 역순으로 만든다는 뜻이다.

---

실제 모습

예제 입력 1 을 토대로, 테이블을 작성하며 어떠한 형식으로 변화하는지 살펴보자 :

N 은 5이므로, 5번까지의 바구니가 있으며, 각각 번호 를 가지고 있다.

생성과 동시에 할당 :

index	0	1	2	3	4
내용물	1	2	3	4	5

i : 1, j : 2

해석 : arr[0] ~ arr[1] 역순

index	0	1	2	3	4
내용물	1	2	3	4	5
변화	2	1	3	4	5

i : 3, j : 4

해석 : arr[2] ~ arr[3] 역순

index	0	1	2	3	4
내용물	2	1	3	4	5
변화	2	1	4	3	5

i : 1, j : 4

해석 : arr[0] ~ arr[3] 역순

index	0	1	2	3	4
내용물	2	1	4	3	5
변화	3	4	1	2	5

i : 2, j : 2

해석 : arr[1] ~ arr[1] 역순

index	0	1	2	3	4
내용물	3	4	1	2	5
변화	3	4	1	2	5

결과

3 4 1 2 5

---

이 정도면 시각적으로 잘 표현했다고 할 수 있다.

그렇다면, 아직 해결되지 않은 관심사항이 남아있다.

그것은 무엇일까?

바로 어떻게 역순으로 만들 것인가? 이다.

1. 초기에는 배열에 바구니의 번호가 순서대로 담겨있는 상태이다 : ex - 1, 2, 3, 4, 5
2. 1 번부터 3 번까지 역순으로 만든다고 가정한다.
3. 역순의 상태를 기억할 길이 3의 배열을 만든다.
4. 3 번부터 1번까지 순회하며 임시 배열에 저장한다.
5. 다시 1번부터 3번까지 순회하며 임시 배열에서 기본 배열로 삽입한다.
6. 2번으로 돌아간다.
7. M 번 순회가 끝난 후, 공백과 함께 출력한다.

Answer

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] arr = new int[N];

        for(int i = 0; i < N; i++)
            arr[i] = i + 1;

        // M 번 순회 시작 
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            // I 번 부터 J 번 까지 바구니 역순으로 만들어라.
            int I = Integer.parseInt(st.nextToken());
            int J = Integer.parseInt(st.nextToken());

            // 역순을 기억할 임시 저장소 생성 - 1, 3번 바구니면 3개 생성
            int[] tempArr = new int[J - I + 1]; 

            // j 는 바구니 역순 접근, x 는 0 부터 시작하는 삽입 용도 
            for(int j = J - 1, x = 0; j >= I - 1; j--, x++)
                tempArr[x] = arr[j];

            // j 는 기본 배열의 삽입 용도, 임시 배열은 0 부터 시작하게끔 만듬.
            for(int j = I - 1; j <= J - 1; j++)
                arr[j] = tempArr[j - (I - 1)];
        }

        // 최종 출력은 공백과 함께다. 
        for(int i = 0; i < N; i++)
            System.out.print(arr[i] + " ");
    }
}

i, j 는 대문자로 구별하여 I, J 로 받았다.

이는 몇 번째를 의미하는데, 실제 배열의 1 번째는 0 번 인덱스와 동일하므로,

실제 배열 접근 시 I - 1 or J - 1 로 계산된다.