백준 10813번 [공 바꾸기](JAVA) -yes6686- 티스토리

백준 문제 풀이: 10813 [공 바꾸기]

---

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

문제 설명:

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(); // 두 번째 위치

            // 두 위치의 공을 교환
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

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

예제 입력:

5 4
1 2
3 4
1 4
2 2

예제 출력:

4 2 1 3 5

---

코드 설명

• 핵심 알고리즘: 배열을 사용하여 공 번호를 저장하고, 주어진 위치의 값을 교환하는 작업을 반복합니다.
• 구현 세부사항:
  • 초기화 단계에서 배열 arr를 1번부터 N번까지 채웁니다.
  • 연산마다 입력받은 두 위치 a, b의 값을 교환합니다.
  • 최종적으로 배열의 1번부터 N번까지 값을 출력합니다.
• 시간 복잡도 분석:
  • 초기화 단계: O(N)
  • 연산 수행: O(M), 각 연산은 상수 시간에 수행
  • 결과 출력: O(N)
  • 총 시간 복잡도: O(N + M)

---

결과

코드는 정확히 M번의 공 바꾸기 연산을 수행한 후, 공의 최종 위치를 출력합니다. 배열을 이용한 단순한 구현 문제로, 기본적인 배열 조작 및 교환 연산을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!