[정렬] 두 배열의 원소 교체

⭐ 성찰

그리디로 풀 수 있는 정당성을 찾는 것이 중요:

a와 b 원소를 바꾸는 경우, 바꾼 원소는 이후 b의 어느 다른 나머지 원소와 비교하더라도, 크기 때문에 다시 바뀌지 않는다는 점에서 하단의 전략이 유효!

리스트.index('값')을 통해 특정 값의 첫번째 인덱스 접근 가능.

만약, 정당하지 않을 경우에는 삽입, 제거에 각각 O(logn)이 소요되는 힙을 사용해 풀이할 수 있음.

❓ 문제 상황

이코테 p.182
첫 째 줄에 n, k가 공백으로 입력.
- n = 배열 내 원소 수, 최대 100,000
- k = 최대 변경 가능 횟수, <= n
둘째 줄에 공백으로 구분한 a 배열, 셋째 줄에 공백으로 구분한 b 배열이 주어짐.
최대 k번의 바꿔치기 연산을 수행하여 만들 수 있는 배열 a의 모든 원소의 최댓값 출력하라.

👨‍💻 문제 해결: 그리디 + 정렬 OR 힙정렬

✅ 1차 풀이: 시간 초과 발생

input 받아 리스트에 정리
k가 0이 아닌 동안, a의 최소값과 b의 최대값을 비교하여 a 최소값 < b 최대값인 경우만 교환 수행.
- 충족하지 않는 경우 즉시 중단
총합 반환
- 위와 같이 문제를 푸는 경우, O(k n)의 시간 복잡도 발생하여 최악의 경우 100,000 100,000 의 시간 복잡도로 시간 초과 발생 가능.
```
n, k = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
```

while k > 0: min_a = min(a) max_b = max(b) if min_a >= max_b: break else: a[a.index(min_a)], b[b.index(max_b)] = b[b.index(max_b)], a[a.index(min_a)] k -= 1

print(sum(a))


### ✅ 2차 풀이: 사전 정렬을 통한 시간 초과 해결 + 그리디
- a, b를 각각 오름차순 내림차순으로 우선 정렬한 뒤, 첫째 인덱스부터 순서대로 확인. 
    - **이 때, a와 b 원소를 바꾸는 경우, 바꾼 원소는 이후 b의 어느 다른 나머지 원소와 비교하더라도, 크기 때문에 다시 바뀌지 않는다는 점에서 하단의 전략이 유효함.**
```python
a.sort()
b.sort(reverse=True)

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

print(sum(a))

✅ 3차 풀이: 확장성을 고려해 heap을 이용해 풀이

만약 이 때, a와 b 원소를 바꾸는 경우, 바꾼 원소는 이후 b의 어느 다른 나머지 원소와 비교하더라도, 크기 때문에 다시 바뀌지 않는다는 점이 유효하지 않다고 하면, 최대힙과 최소힙을 이용해 풀어주어야 함.
1. a를 최소힙, b를 최대힙으로 구현해 a의 최소 원소와 b의 최대 원소를 비교함
2. 비교시 a의 원소가 크거나 같다면 교체를 종료함.
3. 그 외의 경우에는 최소힙에 꺼낸 b의 최대 원소를 최대힙에 꺼낸 a의 최소 원소를 넣어 교체를 진행함.
  - 이 때, 삽입에는 O(logn) 소요
따라서 a, b 힙을 만드는데 각각 nlogn, k번 꺼내 비교하고, 이를 다시 삽입하는데 2klogn이 소요되어 O(nlogn)의 시간복잡도 내에서 해결할 수 있음.
```
import sys
from heapq import heapify, heappop, heappush
```

input = sys.stdin.readline n, k = map(int, input().split()) a = list(map(int, input().split())) b = list(map(int, input().split()))

def solution(a, b): heapify(a) b = [(-x, x) for x in b] heapify(b)

for i in range(k): min_a = heappop(a) temp = heappop(b) max_b = temp[1] if min_a >= max_b: break else: heappush(a, max_b) heappush(b, (-min_a, min_a)) return sum(a)

print(solution(a, b))

ericagong / algorithm_solving