Search

두 배열의 원소 교체

문제 : 두 배열의 원소 교체

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

문제

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

입력 조건

첫 번째 줄에 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
Python

출력 예시

26
Python

모범 답안

해결에 필요한 핵심 아이디어: 매번 배열 A의 가장 작은 원소를 골라서 배열 B의 가장 큰 원소와 교체

해결 시나리오

1.
배열 A의 가장 작은 원소를 골라서 배열 B의 가장 큰 원소와 교체
Min(A)가 Max(B)보다 작을 때만
배열 A는 오름차순, 배열 B는 내림차순 정렬
2.
두 배열의 원소의 최대 개수를 계산해서 O(NlogN)을 보장하는 정렬 알고리즘 사용
답안

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.