[백준] ✔️10811 바구니 뒤집기 (설명/코드/정답)

 

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

 

 

 

1. 요구 사항 이해

시간, 메모리 제한 : 1초 / 256  MB

 

N개의 바구니가 1부터 N까지 번호가 매겨져 순서대로 일렬로 놓여있다.

M번에 걸쳐 주어진 범위의 바구니 순서를 역순으로 변경한다.

첫 줄에 바구니 개수 N (1 ≤ N ≤ 100)과 연산 횟수 M (1 ≤ M ≤ 100).

다음 M개의 줄에 i, j (1 ≤ i ≤ j ≤ N)가 주어짐. i번째부터 j번째 바구니 순서를 역순으로 변경.

모든 연산을 완료한 후, 바구니 번호를 왼쪽부터 순서대로 출력.

 

 

2. 설계/검증 

 

복잡도

시간 복잡도	최악의 경우	공간 복잡도
O( N + MN )		O(N)

 

배열 초기화는 N개의 바구니에 대해 1부터 N까지 숫자를 할당하므로 O(N)의 시간 복잡도를 가집니다.

특정 구간을 역순으로 바꾸는데, 최악의 경우 N개의 요소를 반으로 나누어 역순으로 바꿔야 합니다.

즉, 한 번의 역순 바꾸기는 최대 O(N/2)의 시간 복잡도를 가집니다

따라서 M번의 명령어 처리는 O(M * (N/2))  시간 복잡도는 O(N+MN)

최악의 경우에도 N과 M이 각각 100이므로 문제의 제한 내에서 효율적으로 수행된다

 

N개의 바구니를 저장하는 배열을 사용하므로 공간 복잡도는 O(N)  

 

 

 

 

3. 정상 코드

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int N = scan.nextInt(); // 가지고 있는 바구니 수
        int M = scan.nextInt(); // 역순 작업을 반복할 횟수

        // 유효성 검사
        if (N < 1 || N > 100 || M < 1 || M > 100) {
            System.out.println(" N 범위 : 1 ≤ N ≤ 100, M 범위 : 1 ≤ M ≤ 100");
            return;
        }

        // 바구니의 번호를 저장할 배열 선언과 초기화
        int[] baskets = new int[N];
        for (int i = 0; i < N; i++) {
            baskets[i] = i + 1;

        }

        // 역순 작업
        while (M-- > 0) {
            int i = scan.nextInt();
            int j = scan.nextInt();

            // 유효성 검사
            if (i < 1 || j < 1 || i > N || j > N || i > j) {
                System.out.println("1 ≤ i ≤ j ≤ N");
                return;
            }

            reverse(baskets, i - 1, j - 1);
        }
        // 결과 출력
        for (int basket : baskets) {
            System.out.print(basket + " ");
        }
        scan.close();
    }

    public static void reverse(int[] array, int start, int end) {
        while (start < end) {
            int temp = array[start];
            array[start] = array[end];
            array[end] = temp;
            start++;
            end--;
        }
    }
}

 

 

 

 

 

추가 정리

while 반복문 범위

while( M--  > 0 ){

 

}