[정렬 알고리즘] 문제3 - 두 배열의 원소 교체(182p)

[이코테] 문제3 - 두 배열의 원소 교체(182p)

(한줄평) 정렬만 할 줄 안다면 쉽게 해결할 수 있는 문제

풀이 시간: 10분 이내

 

1) 문제 해결 아이디어

배열의 크기: n, swap 가능 횟수: k 라고 주어졌을 떄

A, B 2가지 배열의 원소를 각각 하나씩 swap하여 만들 수 있는 A의 원소 합의 최댓값을 구하는 문제다.

 

A, B의 원소를 서로 바꿔 A의 원소 합이 최댓값이 되게 하려면 단순하게 A의 작은 수와 B의 큰수를 바꾸는 것을 최대 K번 반복하면 된다. 그러므로 A는 오름차순 정렬, B는 내림차순 정렬하여 0번부터 (k - 1)번 까지 값을 swap하면 된다. 여기서 중요 포인트는 A, B를 각각 정렬 해야함을 떠올리는 것이다.

단, A의 원소가 B의 원소보다 크거나 같으면 굳이 바꿀 필요가 없다!!! 이 조건을 빼먹지 않아야 한다.

 

2) 소스코드

n, k = map(int, input().split())  # 배열 크기, swap 연산 횟수
a = list(map(int, input().split())) 
b = list(map(int, input().split())) 

# A 오름차순 정렬, B 내림차순 정렬
a.sort()
b.sort(reverse=True)
# 두 배열의 원소 k번 비교
for i in range(k):
  # a가 b보다 크거나 같으면 swap 종료
  if a[i] >= b[i]:  break
  a[i], b[i] = b[i], a[i]
print(sum(a))​