문제 출처
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 06 - 실전문제 4. 두 배열의 원소 교체
제한
- 시간 제한 : 2 초
- 메모리 제한 : 128 MB
문제
- 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.
- N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
입력
- 첫째 줄에 N, K가 공백으로 구분되어 입력된다. (1 <= N <= 100,000,0 <= K <= N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
출력
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
👀 풀이
배열 A의 최솟값을 배열 B의 최댓값과 K번만큼 바꿔가면 된다.- 그럴려면
배열 A는 오름차순 정렬, 배열 B는 내림차순 정렬을 해야 한다.
- 그 후
0번째부터 K - 1번째 원소까지 두 배열의 원소를 바꿔주면 되는데 배열 A의 i번째 원소가 배열 B의 i번째 원소보다 작을 때에만 바꿔준다. 만약 배열 A의 i번째 원소가 배열 B의 i번째 원소보다 크다면 거기부터는 배열 B의 원소가 항상 작은 것이기 때문에 남은 K번만큼 계속 바꾸면 오답을 받게 될 것이다.
코드
