실전 문제 - 두 배열의 원소 교체

문제

동빈이는 두 개의 배열 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

 

 

문제 해설

N개의 원소를 가지고 있는 A와 B를 최대 K번 바꿔치기해서 A의 모든 원소의 합을 최대로 만들어야 한다.

컨셉은 단순하다. A에서 가장 작은 원소와 B의 가장 큰 원소를 바꿔주면 된다. 하지만 무조건 바꿔주는 것이 아니라 A의 가장 작은 원소가 B의 가장 큰 원소보다 작은 경우에만 바꿔야 한다.

 

그러므로 A를 오름차순으로 정렬하고, B를 내림차순으로 정렬한 뒤에 인덱스를 0부터 돌면서 각 인덱스에 따른 값이 A가 더 작으면 바꾸고 B가 더 작으면 바꾸지 않으면 된다.

 

#N,K 입력
N, K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

#A는 오름차순, B는 내림차순으로 정렬한다.
A.sort()
B.sort(key=lambda x : -x)

#A의 원소가 더 작으면 swap
for i in range(K):
    if A[i]<B[i]:
        A[i], B[i] = B[i], A[i]
    else:
        break

#A의 합을 출력
print(sum(A))