두 배열의 원소 교체

• 다른 문제 두 개 있는데, 너무 쉽고 예전에 풀어본 문제라 안품

메모

두 배열 A B

• 각 원소는 동일하게 n개씩

최대 k번의 바꿔치기를 해서
A배열의 총합이 최대가 되도록 하는 것

• 출력결과 : 총합 max값

알고리즘 및 방법

방법은 두가지일듯

1)
a배열에선 min값 k개
b배열에선 max값 k개 추출해서 바꾼다
-> min, max 매번 O(N)이라 시간폭탄일수도
-> 그리고 중간값을 바꾸면 뒤에 데이터를 한칸씩 옮기는 시간도 고려해야할수도

2)

a정렬시킴 (->오름차순)
b정렬시킴 (->내림차순)

=> 같은 idx에 있는 것끼리 교환 to k까지

for i in range(k):
    a[i], b[i] = b[i], a[i]
    ans = max(ans, sum(a))

솔루션 코드 - 내가 푼

• 동빈나 정답이랑 같지만 다른점은
  • a[i]가 b[i]보다 커지는 경우 break를 걸어주지 않았다
    • 더 작은데 굳이 바꿔줄 필요가 없으니까!!
  • 이렇게 할 경우 시간을 더 줄일 수 있다!

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

a = sorted(a)
b = sorted(b, reverse = True)
ans = sum(a)

for i in range(k):
    a[i], b[i] = b[i], a[i]
    ans = max(ans, sum(a))

print(a)
print(b)
print(ans)

---

솔루션 코드 - 동빈나

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

a = sorted(a)
b = sorted(b, reverse = True)

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

print(a)
print(b)
print(sum(a))

---

솔루션 코드 - cpp

• sort함수 역순정렬 사용법 주의
• c++ swap 함수 있다

#include <bits/stdc++.h>
using namespace std;

// (중요) 역순으로 정렬하기 위한 (반드시 'x > y' 로)
bool compare(int x, int y) {
	return x > y;
}

int main(void) {
	int n, k;
	vector <int> a;
	vector <int> b;
	long long ans = 0;   // (중요) 합 결과가 매우 큰 수일 수 있으므로 long long 선언

	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		a.push_back(t);
	}
		
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		b.push_back(t);
	}
	
	sort(a.begin(), a.end());
	sort(b.begin(), b.end(), compare); // (중요) 역순으로 정렬하기 위한 (반드시 'x > y' 로)

	for (int i = 0; i < k; i++) {
		// (중요) swap 함수
		if (a[i] < b[i]) {
			swap(a[i], b[i]);
		}
		else
			break;
	}

	for (int i = 0; i < n; i++)
		ans += a[i];

	cout << ans << endl;
	return 0;
}