BOJ 10813 - 공 바꾸기

문제

N개의 바구니에 1부터 N까지 공이 담겨 있을 때, M번의 교환을 수행한 결과를 출력하라.

입력

첫째 줄에 N과 M, 이후 M줄에 교환할 바구니 번호 쌍이 주어진다.

출력

1번부터 N번 바구니에 담긴 공 번호를 공백으로 구분하여 출력한다.

예제

입력	출력
`5 4` `1 2` `3 4` `1 4` `2 2`	`3 1 4 2 5`

풀이

배열로 바구니를 표현하고, M번의 교환을 시뮬레이션한다.

크기 N+1 배열을 만들어 bucket[i] = i로 초기화한다
M번 반복하며 두 바구니의 공을 swap한다
최종 배열 상태를 출력한다

핵심 아이디어: 배열 인덱스 교환(swap)으로 바구니 내용물 변경을 시뮬레이션한다.

코드

package day749;
 
import java.util.*;
import java.io.*;
 
public class Day712BOJ10813공바꾸기 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    StringTokenizer st;
 
    int N, M;
 
    st = new StringTokenizer(br.readLine());
 
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());
 
    int[] bucket = new int[N + 1];
 
    for (int i = 1; i <= N; i++) {
      bucket[i] = i;
    }
 
    for (int i = 0; i < M; i++) {
      st = new StringTokenizer(br.readLine());
      int a = Integer.parseInt(st.nextToken());
      int b = Integer.parseInt(st.nextToken());
 
      int temp = bucket[a];
      bucket[a] = bucket[b];
      bucket[b] = temp;
    }
 
    for (int i = 1; i < N + 1; i++) {
      sb.append(bucket[i] + " ");
    }
    System.out.println(sb);
  }
}

복잡도

시간: O(N + M) — 초기화 O(N) + 교환 O(M)
공간: O(N) — 바구니 배열

문제