[JAVA]백준 알고리즘 10811번 : 바구니 뒤집기

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

10811번: 바구니 뒤집기

문제

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

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

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

 

풀이

바구니의 순서를 주어진 만큼 역순으로 뒤집는 문제이다.

백준 알고리즘 10813번 : 공 바꾸기 문제에서 공의 자리를 바꾸는 방법을 활용하면 어렵지 않게 해결할 수 있다.

 

해당 방법은 아래와 같고, 처음 본다면 공 바꾸기 문제의 설명을 참고하시길 바란다.

int tmp = basket[I];
basket[I] = basket[J];
basket[J] = tmp;

 

이 문제에서 주의할 점이 한 가지 있다.

위 방법을 반복문을 사용하면 해결할 수 있는데, 반복문의 범위를 설정하는 것이 조금 헷갈린다.

결론을 말하자면, I번 바구니부터 J번 바구니까지의 번호를 역순으로 바꿀 때

I번째부터 (I + J) / 2 번째까지만 수행해야 한다.

I번째부터 J번째까지 다 수행하게 될 경우, 다시 원상복구가 될 것이기 때문이다.

 

아래 그림은 이해를 돕기 위해 1번째부터 6번째까지 수행할 경우의 과정을 나타낸 그림이다.

그림을 보면, (1 + 6) / 2인 3번째까지 수행하였을 때 바구니의 순서가 역순이 된다는 것을 알 수 있다.

 

 

---

🔔 자세한 코드 설명은 더보기 란에 작성하였습니다.

1. N, M을 입력받는다.

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

 

2. basket 배열을 문제에 주어진 초기 상태에 맞게 초기화한다.(1번부터 N번까지 사용하기 위해 크기를 N + 1로 하였다.)

int[] basket = new int[N + 1];
for(int i = 1; i <= N; i++) {
    basket[i] = i;
}

 

3. M번의 바구니 뒤집기를 수행한다. (J + I - j는 j와 대칭인 위치에 있는 index이다.)

for(int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int I = Integer.parseInt(st.nextToken());
    int J = Integer.parseInt(st.nextToken());

    for(int j = I; j <= (I + J) / 2; j++) {
        int tmp = basket[j];
        basket[j] = basket[J + I - j];
        basket[J + I - j] = tmp;
    }
}

 

4. 조건에 맞게 StringBuilder 클래스를 사용하여 출력한다.

for(int i = 1; i <= N; i++) {
    sb.append(basket[i]).append(" ");
}
System.out.println(sb);

---

코드

BufferedReader 클래스와 StringBuilder 클래스를 이용한 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] basket = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            basket[i] = i;
        }
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int I = Integer.parseInt(st.nextToken());
            int J = Integer.parseInt(st.nextToken());

            for(int j = I; j <= (I + J) / 2; j++) {
                int tmp = basket[j];
                basket[j] = basket[J + I - j];
                basket[J + I - j] = tmp;
            }
        }
        for(int i = 1; i <= N; i++) {
            sb.append(basket[i]).append(" ");
        }
        System.out.println(sb);
    }
}

 

틀린 부분이 있다면 정정해 주시면 감사하겠습니다.
궁금한 부분이 있거나, 다른 아이디어가 있으시면 자유롭게 댓글 남겨주세요!