[정렬] 이코테 두 배열의 원소 교체(Java)

📚 문제

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

동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는

원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가

되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.

 

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

 

📝 문제 해결

배열 A의 가장 작은 원소와 배열 B의 가장 큰 원소를 교체해줘야함
배열 A는 오름차순으로 배열 B는 내림차순으로 정렬하여 첫 번째 인덱스부터 차례대로 비교한 뒤,

A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다.

 

이때 두 배열의 원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 정렬알고리즘을 이용해야 한다!

 

💻 코드

package sorting;

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class sorting08 {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);

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

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

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

        Arrays.sort(a); //오름차순 정렬
        Arrays.sort(b, Collections.reverseOrder()); //내림차순 정렬

        for(int i=0; i<k; i++){
            if(a[i] < b[i]){
                int temp = a[i];
                a[i] = b[i];
                b[i] = temp;
            }else break;
        }

        int sum = 0;
        for(int i=0; i<n; i++){
            sum += a[i];
        }

        System.out.println(sum);
    }
}

 

내림차순 정렬
내림차순 정렬을 위해서는 primitive type이 아니라 Wrapper 클래스로 선언해야 한다. 그 이유는 Collections에 도움을 받아야 하기 때문이다. 

Integer[] a = new Integer[n]; //Wrapper 클래스를 활용하여 선언
Arrays.sort(a, Collections.reverseOrder());​