[백준] 10813 공 바꾸기 (설명/코드/정답)

 

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

 

 

 

 

1. 요구 사항 이해

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

 

N개의 바구니에 1부터 N까지 번호가 적힌 공을 넣고, M번의 교환 작업을 통해 바구니에 들어있는 공의 최종 상태를 출력하는 프로그램 작성. 

 

- 1 ≤ N ≤ 100

- 1 ≤ M ≤ 100

- i번 바구니와 j번 바구니에 들어있는 공을 교환  1 ≤ i ≤ j ≤ N

 

 

2. 설계/검증 

 

복잡도

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

 

배열 초기화: 배열 baskets를 초기화하는데 O(N) 시간이 걸립니다. 공 교환 작업: M개의 교환 작업 각각에 대해 O(1) 시간 복잡도가 필요하므로 총 O(M) 시간이 걸립니다. 전체 시간 복잡도는 O(N) + O(M)로,  여기서 N과 M 모두 100 이하의 상수이므로, 시간 복잡도는 O(1)

 

배열 저장: baskets 배열을 사용하므로 O(N) 공간이 필요합니다. 이 배열은 바구니 개수와 동일한 크기를 가지며, baskets 외에는 추가적인 메모리 사용이 없습니다. 공간 복잡도는 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[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = i + 1;
        }


        // 공 교환
        for (int x = 0; x < M; x++) {
            int i = scan.nextInt();
            int j = scan.nextInt();

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

            int temp = nums[i - 1];
            nums[i - 1] = nums[j - 1];
            nums[j - 1] = temp;
        }

        //결과 출력
        for (int num : nums) {
            System.out.print(num + " ");
        }

        scan.close();
    }
}