[Python] 이것이 코딩테스트다 with 파이썬 - 정렬 - 두 배열의 원소 교체

들어가기 앞서

 

 

해당 문제 및 해설은 "이것이 코딩 테스트다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.

책에서는 정렬하는 코드 함수를 sorted 를 활용하였지만, 필자의 경우 sort 를 사용하였습니다.
이 점은 참고 부탁드립니다.

 

 

이것이 코딩테스트다 with 파이썬 책 구매 사이트

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

 

---

 

정렬 알고리즘

 

 

정렬이란, 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
알고리즘 효율성을 쉽게 이해할 수 있는 정렬을 통하여 코딩 테스트 합격률을 높여보도록 한다. 
정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 정리 해보려고 한다.

 

 

---

 

 

문제 설명 : 정렬 - 두 배열의 원소 교체

 

 

두 배열 A 와 B 가 있습니다. 두 배열은 N 개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수 이다.
최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A 에 있는 원소 하나와 배열 B 에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다.
최종 목표는 배열 A 의 모든 원소의 합이 최대가 되도록 하는 것이다.

N, K 그리고 배열 A 와 B 의 정보가 주어졌을 때, 최대 K 번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 A 모든 원소의 합의 최댓값을 출력하는 프로그램을 작성하시오.

 

 

예) N = 5, K = 3, 그리고 배열 A, B 는 다음과 같다.

 

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

 

이 경우에는, 다음과 같이 세 번의 연산을 수행 할 수 있다.

 

• 연산 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 과 K 입력 받기

n, k = map(int, input().split())

# A, B 리스트 입력 받기
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a.sort()
b.sort(reverse = True)

result = 0

for i in range(k) :
  if a[i] < b[i]:
    a[i], b[i] = b[i], a[i]
  else:
    break

result = sum(a)

print(result)