[이코테 with Java] 두 배열의 원소 교체

문제

동빈이는 두 개의 배열 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이 되며, 이보다 더 합을 크게 만들 수는 없다. 

따라서 이 예시의 정답은 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

 

---

1. 나의 코드

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int k = scanner.nextInt();

        int[] arr = new int[N];
        Integer[] arr2 = new Integer[N];

        for(int i = 0; i < N; i++){
            arr[i] = scanner.nextInt();
        }

        for(int i = 0; i < N; i++){
            arr2[i] = scanner.nextInt();
        }


        Arrays.sort(arr);
        Arrays.sort(arr2, Collections.reverseOrder());

        int count = 0;
        for(int i = 0; i < k; i++){
            if(arr[i] < arr2[i]){
                arr[i] = arr2[i];
            }
        }

        for(int i = 0; i < N; i++){
            count += arr[i];
        }
        System.out.print(count);



    }
}

 

나는 정수 배열을 입력받아 정렬을 해줬다.

출력을 담당할 첫 번째 A 배열은 오름차순으로, 원소 바꿔치기를 도와줄 두 번째 B 배열은 내림차순(역순)으로 정렬해주었다. 

그리고 0부터 순차적으로 A 배열과 B 배열을 비교하며 B 배열의 원소가 더 크다면 바꾸고, 값을 더해서 출력해주었다.

 

2. 종빈님의 코드

import java.util.*;

public class Main {

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

        // N과 K를 입력받기
        int n = sc.nextInt();
        int k = sc.nextInt();

        // 배열 A의 모든 원소를 입력바딕
        Integer[] a = new Integer[n];
        for (int i = 0; i < n; i++){
            a[i] = sc.nextInt();
        }

        // 배열 B의 모든 원소를 입력받기
        Integer[] b = new Integer[n];
        for (int i = 0; i < n; i++){
            b[i] = sc.nextInt();
        }

        // 배열 A는 오름차순 정렬 수행
        Arrays.sort(a);
        // 배열 B는 내림차순 정렬 수행
        Arrays.sort(b, Collections.reverseOrder());

        // 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교
        for(int i = 0; i < k; i++){
            // A의 원소가 B의 원소보다 작은 경우
            if (a[i] < b[i]) {
                // 두 원소를 교체
                int temp = a[i];
                a[i] = b[i];
                b[i] = temp;
            }
            // A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
            else break;
        }

        // 배열 A의 모든 원소의 합을 출력
        long result = 0;
        for(int i = 0; i < n; i++){
            result += a[i];
        }
        System.out.println(result);
    }
}

 

종빈님과 나의 코드가 유사하지만, 한 가지 다른 점이 있다.

종빈님은 A의 원소가 B의 원소보다 크거나 같으면 반복문을 탈출하도록 했다.