[백준] 10811번: 바구니 뒤집기 - JAVA

[작성일: 2023. 08. 27]

 

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

 

 

풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.valueOf(st.nextToken());  // 바구니의 수
        int m = Integer.valueOf(st.nextToken());  // m번 바구니의 순서부터 역순으로

        int[] basket = new int[n];

        for (int i = 0; i < basket.length; i++) {
            basket[i] = i + 1;
        }

        for (int i = 0; i < m; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine());
            int start = Integer.valueOf(st2.nextToken());
            int end = Integer.valueOf(st2.nextToken());

            for (int j = 0; start+j < end-j; j++) {
                int tmp = basket[start + j - 1];
                basket[start + j - 1] = basket[end - j - 1];
                basket[end - j - 1] = tmp;
            }
        }

        for (int i = 0; i < basket.length; i++) {
            bw.write(basket[i] + " ");
        }
        br.close();
        bw.flush();
        bw.close();
    }
}

 

예제로 풀어서 설명하면 도현이는 바구니 5개를 가지고 있고 1번부터 5번까지의 바구니를 가지고 있다. [1 2 3 4 5]

1 2 를 입력받으면 1번부터 2번 바구니의 순서를 역으로 바꾸면 된다. 그럼 [2 1 3 4 5]가 된다. 

3 4 를 입력받으면 3번부터 4번까지의 바구니 순서를 역으로 바꾸면 된다. [2 1 4 3 5]

1 4 를 입력받으면 1번부터 4번까지의 바구니 순서를 역으로 바꾸면 된다. [3 4 1 2 5]

2 2 를 입력받았을 경우에는 바구니의 순서에 영향이 없다.

 

이 문제를 해결하려면 start(바구니 시작 순서)와 end(바구니 끝 순서)를 입력 받고, tmp(임시 변수)를 선언해야 한다.

for(j=0, j+start<end-j; j++)로 작성한 이유는 start가 1이고 end가 4일 때, 처음에는 j가 0이고 1<4가 된다.

현재 바구니가 2 1 4 3 5라고 가정할 때, basket[start + j - 1]인 basket[0]에 있는 2와 basket[end - j - 1]인 basket[3]에 있는 3의 위치를 바꾼다. (바구니는 3 1 4 2 5가 된다.)

 

그 다음 증감 연산자로 인해 j가 1이 되고 2<3가 된다.  현재 바구니는 3 1 4 2 5이다.

basket[start + j - 1]은 basket[1]이고 basket[end - j - 1]은 basket[2]이다. 이 둘의 위치를 바꾸면 3 4 1 2 5가 된다.