# [이.취.코] Chap 6. 정렬 - 두 배열의 원소 교체

- Author: @mildsalmon
- Published: 2021-08-18
- Updated: 2021-08-29
- Source: http://blex.me/@mildsalmon/char-6-%EC%A0%95%EB%A0%AC-%EB%91%90-%EB%B0%B0%EC%97%B4%EC%9D%98-%EC%9B%90%EC%86%8C-%EA%B5%90%EC%B2%B4
- Tags: 파이썬, 한빛미디어, 나동빈, 코딩테스트, 문제, 풀이, 정렬, 두배열의원소교체

---

# 1. 두 배열의 원소 교체

- 난이도
	- 하
- 풀이 시간
	- 20분
- 시간 제한
	- 2초
- 메모리 제한
	- 128MB
- 기출
	- 국제 알고리즘 대회

### A. 문제

두 개의 배열 A와 B가 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다.

배열 A의 원소와 배열 B의 원소를 최대 K번 바꿀 수 있다.

최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는 것이다.

##### a. 예를 들면. 

N = 5, K = 3

A = [1, 2, 5, 4, 3]
B = [5, 5, 6, 6, 5]

일때.

K(3)번 연산을 수행하여 아래와 같이 된다.

A = [6, 6, 5, 4, 5]
B = [5, 1, 2, 3, 5]

여기서 A의 합은 26이다.

##### b. 입력 조건

- 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다.
	- 1 <= N <= 100,000
	- 0 <= K <= N
- 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다.
	- 모든 원소는 10,000,000보다 작은 자연수이다.
- 세 번째 줄에는 배열 B의 원소들이 공백으로 구분되어 입력된다.
	- 모든 원소는 10,000,000보다 작은 자연수이다.

##### c. 출력 조건

- 최대 K번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A의 모든 원소의 합의 최댓값.

##### d. 테스트 케이스

- 입력 예시

	```

	5 3  
  	1 2 5 4 3  
	5 5 6 6 5

	```

- 출력 예시

	```

	26

	```
	
### B. 내 답안

```python

# n, k = list(map(int, input().split()))  
  
# A = list(map(int, input().split()))  
# B = list(map(int, input().split()))  
  
n, k = 5, 3  
  
A = [1, 2, 5, 4, 3]  
B = [5, 5, 6, 6, 5]  
  
A.sort()  
B.sort(reverse=True)  
  
print(A)  
print(B)  
  
for i in range(k):  
    A[i], B[i] = B[i], A[i]  
  
result = sum(A)  
  
print(result)

```

##### a. 회고

> 분석

빨리 풀어야지 하다가, 조건 하나를 빼먹었다. A의 최댓값을 구하는 것이라 A와 B를 교체할 때 B의 원소가 A의 원소보다 작으면 교체하지 않는다는 조건을 빼먹었다.

> 반성

쉬운 문제인데도 이렇게 틀리는 구나 싶었다. 조건을 똑바로 읽고 메모해야겠다.

### C. 문제 해설

배열 A에서 가장 작은 원소를 골라서, 배열 B에서 가장 큰 원소와 교체를 하는 것이다.

단, 배열 A에서 가장 작은 원소가 배열 B에서 가장 큰 원소보다 작을 때에만 교체를 수행한다.

이런 과정을 K번 반복하면 정답을 얻을 수 있다.

배열 A의 원소를 오름차순으로 정렬하고, 배열 B의 원소를 내림차순으로 정렬한다. 그리고 두 원소를 가장 첫 번째 인덱스부터 차례대로 비교하면서 A의 원소가 B의 원소보다 작을 때에만 교체를 수행한다.

원소가 최대 100,000개까지 입력될 수 있으므로 O(NlogN)을 보장하는 알고리즘을 사용해야 한다.

##### a. 책 답안

[python-for-coding-test/12.py at master · ndb796/python-for-coding-test (github.com)](https://github.com/ndb796/python-for-coding-test/blob/master/6/12.py)

# 참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #문제 #풀이 #정렬 #두배열의원소교체