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

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

 

 

 

---

문제

 

 

---

해결 방법

이 문제는 배열을 사용하여 바구니의 상태를 관리하고, 주어진 범위의 순서를 바꾸는 연산을 수행하면 된다. 핵심 로직은 특정 범위를 역순으로 만드는 것으로, 이를 위해 투 포인터(양 끝에서 중앙으로 이동하며 값 교환) 방법을 사용할 수 있다.

 

해결 방법

1. 초기 상태에서 바구니 번호를 arr[i] = i 형태로 저장한다.

2. M번의 연산을 수행하면서 주어진 범위의 숫자를 역순으로 변경한다.

3. 마지막으로 배열의 값을 출력한다.

 

---

코드 

 

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

public class Main {
    static int[] arr; // 바구니 배열

    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()); // 연산 개수
        
        arr = new int[n+1];
        for (int i = 1; i <= n; i++) {
            arr[i] = i; // 초기 바구니 상태 저장
        }
        
        for (int k = 0; k < m; k++) {
            st = new StringTokenizer(br.readLine());
            int i = Integer.parseInt(st.nextToken()); // 역순 시작 위치
            int j = Integer.parseInt(st.nextToken()); // 역순 종료 위치
            if (i == j) continue; // i와 j가 같으면 변경할 필요 없음
            reverse(i, j);
        }
        
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i <= n; i++) {
            sb.append(arr[i]).append(" "); // 결과 문자열 생성
        }
        System.out.println(sb);
    }

    public static void reverse(int i, int j) {
        while (i < j) { // 양 끝에서 중앙으로 이동하며 값 교환
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            i++;
            j--;
        }
    }
}

 

 

---

코드 설명

1. 초기

• arr 배열을 선언하고, 1부터 N까지 값을 채운다.

 

2. 입력 처리 및 연산

• BufferedReader와 StringTokenizer를 사용하여 입력을 받는다.
• M번 반복하여 주어진 범위의 바구니를 역순으로 바꾼다.

 

3. 역순 변환 함수 (reverse)

• i부터 j까지의 값을 교환하는 방식으로 역순으로 변경한다.
• i < j 조건이 만족하는 동안, i와 j를 변경하면서 점진적으로 중앙으로 이동한다.

 

예제 테스트

입력

 

5 4
1 2
3 4
1 4
2 2

 

과정

1. 초기 상태: [1, 2, 3, 4, 5]

2. (1,2) 역순: [2, 1, 3, 4, 5]

3. (3,4) 역순: [2, 1, 4, 3, 5]

4. (1,4) 역순: [3, 4, 1, 2, 5]

5. (2,2) 변경 없음

 

출력

3 4 1 2 5

 

---

시간 복잡도 분석

1. 조합의 경우의 수

• N개의 숫자에서 M개를 선택하는 조합의 개수는 C(N, M) = N! / (M! * (N-M)!)이다.
• 최댓값인 N = 8, M = 8일 때 P(8,8) = 8! = 40,320이므로 충분히 해결 가능하다.

 

2. 최악의 경우 시간 복잡도

• 최악의 경우에도 O(2^N) 이하로 수행되며, N ≤ 8이므로 충분히 빠름.

 

 

---

결론

• 각 연산에서 최대 N개의 요소를 교환하며, 총 M번 수행하므로 O(NM)이다.
• N과 M의 최대값이 100이므로 최악의 경우 10,000번 연산이며, 충분히 빠르게 수행 가능하다.