[Algorithm] 두 배열의 원소 교체

문제

동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.

동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

 

입력 조건

첫번째 줄에 n, k가 입력된다.

두번째 줄에 배열 A의 원소, 세번째 줄에 배열 B의 원소가 입력된다.

 

출력 조건

최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최대값을 출력한다.

 

풀이

K번의 바꿔치기 동안, 배열 A의 최소와 배열 B의 최대를 교환한다. K번 동안 만들 수 있는 배열 A의 합의 최대값이기 때문에, 중간에 원소가 더 작은 것으로 교환되는 경우는 막는다.

 

import java.util.*;

class Main {

  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int n = sc.nextInt();
    int k = sc.nextInt();

    int[] a = new int[n];
    int[] b = new int[n];

    for (int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    for (int i = 0; i < n; i++) {
      b[i] = sc.nextInt();
    }
    
    sc.close();

    for (int i = 0; i < k; i++) {
      Arrays.sort(a);
      Arrays.sort(b);
      if (a[0] < b[n-1]) {
        int tmp = a[0];
        a[0] = b[n-1];
        b[n-1] = tmp;
      } else break;
    }
    
    int answer = 0;
    for (int i : a) {
      answer += i;
    }
    System.out.println(answer);

  } // end main
}