[국제 알고리즘 대회] 두 배열의 원소 교체

문제

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

 

N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하라.

 

예를 들어 N = 5, K = 3이고 배열 A와 B가 다음과 같다고 하자.

• 배열 A = [1, 2, 5, 4, 3]
• 배열 B = [5, 5, 6, 6, 5]

이 경우, 다음과 같이 세 번의 연산을 수행할 수 있다.

• 연산 1) 배열 A의 원소 '1'과 배열 B의 원소 '6'을 바꾸기
• 연산 2) 배열 A의 원소 '2'와 배열 B의 원소 '6'을 바꾸기
• 연산 3) 배열 A의 원소 '3'과 배열 B의 원소 '5'를 바꾸기

세 번의 연산 이후 배열 A와 배열 B의 상태는 다음과 같이 구성될 것이다.

• 배열 A = [6, 6, 5, 4, 5]
• 배열 B = [3, 5, 1, 2, 5]

이때 배열 A의 모든 원소의 합은 26이 된다.

 

입력 조건

• 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 <= N <= 100,000, 0 <= K <= N)
• 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
• 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.

출력 조건

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

입력 예시

5 3
1 2 5 4 3
5 5 6 6 5

 

출력 예시

26

---

아이디어

 K 번까지는 B 배열의 최댓값을 A 배열과 바꿀 수 있으므로, 두 배열을 정렬해서 K번까지 비교한다.

A배열은 오름차순으로, B배열은 내림차순으로 정렬하여 B배열 중 A배열보다 큰 수가 있으면 sum 에 더함으로써 실질적으로 바꾸지 않더라도 A배열과 바꾼것과 마찬가지이다.

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Chap06_4 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int[] A = new int[N];
        Integer[] B = new Integer[N];   // 내림차순 정렬하기 위해 Integer 배열 선언
        // 배열 A 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        // 배열 B 입력
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            B[i] = Integer.parseInt(st.nextToken());
        }
        // A는 오름차순, B는 내림차순 정렬
        Arrays.sort(A);
        Arrays.sort(B, Collections.reverseOrder());

        // K번 바꿔치기 하므로, K번까지는 두 배열 중 큰 수를 더하고, 이후에는 A배열의 나머지 원소를 더함
        int sum = 0;
        for(int i=0; i<K; i++) {
            if(B[i] > A[i])
                sum += B[i];
            else
                sum += A[i];
        }
        for(int i=K; i<N; i++) {
            sum += A[i];
        }
        System.out.println(sum);
    }
}