백준 10811번 [바구니 뒤집기](JAVA) -yes6686- 티스토리

백준 문제 풀이: 10811 [바구니 뒤집기]

---

문제 링크: https://www.acmicpc.net/problem/10811

문제 설명:

1번부터 N번까지 번호가 적힌 바구니가 일렬로 배치되어 있습니다. M번의 작업 동안 각 작업에서 바구니의 일부 구간을 선택하여 해당 구간의 순서를 뒤집습니다. 모든 작업이 끝난 후 바구니의 최종 상태를 출력하는 문제입니다.

---

문제 해결 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 입력을 받기 위한 Scanner 객체 생성
        int n = scanner.nextInt(); // 바구니의 개수
        int m = scanner.nextInt(); // 뒤집기 작업의 횟수

        // 바구니 초기화 (1번부터 N번까지 번호)
        int[] arr = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            arr[i] = i;
        }

        // M번의 뒤집기 작업 수행
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt(); // 시작 바구니 번호
            int b = scanner.nextInt(); // 끝 바구니 번호

            // 구간 [a, b]의 순서를 뒤집음
            for (int j = 0; j < (b - a + 1) / 2; j++) {
                int temp = arr[a + j];
                arr[a + j] = arr[b - j];
                arr[b - j] = temp;
            }
        }

        // 결과 출력
        for (int i = 1; i <= n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

예제 입력:

5 3
1 2
3 4
1 5

예제 출력:

5 3 4 1 2 

---

코드 설명

• 핵심 알고리즘: 배열의 일부 구간을 선택하여 반복문을 통해 해당 구간의 순서를 뒤집습니다.
• 구현 세부사항:
  • 초기화 단계에서 배열 arr는 1번부터 N번까지 채워집니다.
  • 각 작업에서 시작 번호 a와 끝 번호 b가 주어지면, 해당 구간의 앞뒤 요소를 반복적으로 교환하여 뒤집기를 구현합니다.
  • 최종적으로 배열의 상태를 출력합니다.
• 시간 복잡도 분석:
  • 초기화 단계: O(N)
  • 뒤집기 작업: O(M * K), 여기서 K는 뒤집기 구간의 평균 크기
  • 결과 출력: O(N)
  • 총 시간 복잡도: O(N + M * K)

---

결과

코드는 정확히 M번의 뒤집기 작업을 수행한 후, 바구니의 최종 상태를 출력합니다. 배열 조작과 구간 반전 작업을 연습하기에 적합한 문제입니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!