두 배열의 원소 교체(p.182) - 정렬(이코테)

---

해설 부분은 책에 내용을 포함하고, 더 추가하여 최대한 자세하게 설명하려고 노력했습니다.

---

 

문제 해설

 

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

 

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

 

예를 들어 N = 5, K =3이고 배열 A와 B가 다음과 같다고 하자.

 

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

 

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

 

• 연산 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이 되며, 이보다 더 합을 크게 만들 수는 없다. 따라서 이 예시의 정답은 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

 

 

 

---

 

문제 해설

 

배열 A와 배열 B를 잘 입력받고, 각각의 배열을 정렬하는데 배열 A는 오름차순 정렬, 배열 B는 내림차순 정렬을 한다. 그 후  배열 A의 가장 작은 원소와 배열 B의 가장 큰 원소를 교환하면 되는데 여기서 배열 B의 가장 큰 원소가 배열 A의 가장 작은 원소보다 작다면, 바꿀 이유가 없다. 

 

책에서 제시하는 해설 코드는 다음과 같다. 

 

n, k = map(int, input().split()) 
a = list(map(int, input().split()))  # 리스트 컴프리핸션 이용해서 값 입력받기
b = list(map(int, input().split()))  

a.sort() # a는 오름차순 정렬
b.sort(reverse=True) # b는 내림차순 정렬 

for i in range(k):
    if a[i] < b[i]:
        a[i], b[i] = b[i], a[i]
    else: # 정렬이 끝났는데 한번이라도 어긋나면 뒤에 내용은 계산할 필요 없으므로 
        break # break문으로 빠져나온다.

print(sum(a))  # 리스트 a의 합 sum(a)

 

각각의 배열을 정렬하는데 a는 오름차순 b는 내림차순으로 정렬한것이 보인다. 

 

if문이 핵심이다. 사실 if문 같은 코드를 적는것도 파이썬의 장점이라고 생각한다. 변수 swap기능이라 부르는데 C/C++ 언어는 int temp를 선언하고 값을 돌려 넣기 하는 방식으로 해결한다. 

else문에서 한번이라도 if문이 성립하지 않으면 바로 break로 반복문을 부셔주면 된다. 

 

더 이상 반복을 수행할 이유가 없어지기 때문이다. 

 

정렬을 활용해서 문제를 해결할 수 있는 좋은 문제라고 생각한다.