Python) 이것이 취업을 위한 코딩테스트다 06 실전문제 4. 두 배열의 원소 교체
문제 출처Permalink
- 이것이 취업을 위한 코딩테스트다 with 파이썬
- Chapter 06 - 실전문제 4. 두 배열의 원소 교체
제한Permalink
- 시간 제한 : 2 초
- 메모리 제한 : 128 MB
문제Permalink
- 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이며, 여러분은 동빈이를 도와야 한다.
- N, K, 그리고 배열 A와 B의 정보가 주어졌을 때, 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.
입력Permalink
- 첫째 줄에 N, K가 공백으로 구분되어 입력된다. (1 <= N <= 100,000,0 <= K <= N)
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다.
출력Permalink
- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력한다.
👀 풀이Permalink
배열 A
의최솟값
을배열 B
의최댓값
과K
번만큼 바꿔가면 된다.- 그럴려면
배열 A는 오름차순 정렬
,배열 B는 내림차순 정렬
을 해야 한다. - 그 후
0
번째부터K - 1
번째 원소까지 두 배열의 원소를 바꿔주면 되는데배열 A
의i
번째 원소가배열 B
의i
번째 원소보다 작을 때에만 바꿔준다. 만약배열 A
의i
번째 원소가배열 B
의i
번째 원소보다 크다면 거기부터는배열 B
의 원소가 항상 작은 것이기 때문에 남은K
번만큼 계속 바꾸면 오답을 받게 될 것이다.
코드Permalink
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
N, K = map(int, input().split()) | |
arrA = list(map(int, input().split())) | |
arrB = list(map(int, input().split())) | |
arrA = sorted(arrA) | |
arrB = sorted(arrB, reverse=True) | |
for i in range(K): | |
if arrA[i] < arrB[i]: | |
arrA[i], arrB[i] = arrB[i], arrA[i] | |
else: | |
break | |
sum = 0; | |
for i in arrA: | |
sum += i | |
print(sum) |