백준 (10811) - 바구니 뒤집기 Java

https://www.acmicpc.net/problem/10811

10811번: 바구니 뒤집기

문제

도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다.

도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

 

입력

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

둘째 줄부터 M개의 줄에는 바구니의 순서를 역순으로 만드는 방법이 주어진다. 방법은 i j로 나타내고, 왼쪽으로부터 i번째 바구니부터 j번째 바구니의 순서를 역순으로 만든다는 뜻이다. (1 ≤ i ≤ j ≤ N)

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

 

출력

모든 순서를 바꾼 다음에, 가장 왼쪽에 있는 바구니부터 바구니에 적혀있는 순서를 공백으로 구분해 출력한다.

 

접근 방법

* 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다.

-> 크기가 N+1인 배열을 만들고, 각 인덱스의 데이터를 인덱스 번호로 초기화한다.
    '순서대로' 적혀 있다고 했으니 1차원 배열을 써도 무난하겠다고 판단!!
    int[] arr = new int[N+1]; // arr[0]을 낭비하긴 하지만, 문제를 해결하는데 있어 편하게 하기 위해서!!

 

* 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2번째 바구니, ..., 가장 오른쪽 바구니를 N번째 바구니라고 부른다. 도현이는 앞으로 M번 바구니의 순서를 역순으로 만들려고 한다. 도현이는 한 번 순서를 역순으로 바꿀 때, 순서를 역순으로 만들 범위를 정하고, 그 범위에 들어있는 바구니의 순서를 역순으로 만든다.

-> 그림과 같이 i는 1씩 증가를, j는 1씩 감소를 하며 양 끝에 있는 값끼리 위치를 바꿔준다. 그리고 i가 j보다 작아질 때라는 조건을 부여하여 탈출 조건을 작성한다.

 

* 바구니의 순서를 어떻게 바꿀지 주어졌을 때, M번 바구니의 순서를 역순으로 만든 다음, 바구니에 적혀있는 번호를 가장 왼쪽 바구니부터 출력하는 프로그램을 작성하시오.

 

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

public class Main {
    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        // 1. N+1 크기의 배열을 만든다. index를 다루기 편하게 하기 위함
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[] arr = new int[N+1];

        // 2. 각 배열의 초기값을 index값과 일치하게 초기화
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }

        for (int k = 0; k < M; k++) {
            int i = sc.nextInt();
            int j = sc.nextInt();

            while (i < j) {
                int temp = arr[i];
                arr[i++] = arr[j];
                arr[j--] = temp;
            }
        }

        for (int answer : arr) {
            if(answer != 0)
                System.out.print(answer + " ");
        }

    }
}

 

정리

while문을 사용하여 양 끝단에서 한 칸씩 줄어들며 버블정렬을 하면 쉽게 풀 수 있는 문제이다.

 

회고

처음에 for 문 안에 i와 j 두 값을 한번에 바꿀 수 없을까?하는 생각에 잠겨서 30분 정도 고민했던 것 같다. 길을 잘못들어섰으면 빨리 뒤돌아서 다른 방법을 찾는 것도 하나의 방법!