두 배열의 원소 교체

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<int> a;
vector<int> b;
bool cmp(int a,int b){
  return a>b;
}

int main() {
  int n,k;
  cin>>n>>k;
  for(int i=0;i<n;i++){
    int num;
    cin>>num;
    a.push_back(num);
  }
  for(int i=0;i<n;i++){
    int num;
    cin>>num;
    b.push_back(num);
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end(),cmp);

  for(int i=0;i<k;i++){
    if(a[i]<b[i])
      a[i]=b[i];
  }
  int sum=0;
  for(int i=0;i<n;i++)
    sum+=a[i];
  cout<<sum;
}

문제는 굉장히 쉬웠다. a벡터는 오름차순 정렬, b벡터는 내림 차순 정렬을 진행 해준다. 책의 예시로 들어보면,

a = 1,2,5,4,3

b = 5,5,6,6,5

일때, 정렬을 진행해주면

a = 1,2,3,4,5

b = 6,6,5,5,5 

가 된다. 이때 앞에서부터 k번만큼 교체를 진행해주면 된다. 이때, a의 가장 작은 원소가 b의 가장 큰 원소보다 큰 경우가 있을 수 있다. 이때는 교체를 진행하면 안되기 때문에 a[i] < b[i] 일때만 교체 해주는 것으로 코드를 작성했다.

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> a, b;

bool compare(int x, int y) {
    return x > y;
}

int main(void) {
    // N과 K를 입력받기
    cin >> n >> k;
    // 배열 A의 모든 원소를 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a.push_back(x);
    }
    // 배열 B의 모든 원소를 입력받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        b.push_back(x);
    }
    // 배열 A는 오름차순 정렬 수행
    sort(a.begin(), a.end());
    // 배열 B는 내림차순 정렬 수행
    sort(b.begin(), b.end(), compare);

    // 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 
    for (int i = 0; i < k; i++) {
        // A의 원소가 B의 원소보다 작은 경우
        if (a[i] < b[i]) swap(a[i], b[i]); // 두 원소를 교체
        // A의 원소가 B의 원소보다 크거나 같을 때, 반복문을 탈출
        else break;
    }

    // 배열 A의 모든 원소의 합을 출력
    long long result = 0;
    for (int i = 0; i < n; i++) {
        result += a[i];
    }
    cout << result << '\n';
}

정답코드에서는 result 변수를 long long형으로 선언하였다. 문제 조건을 잘 보니까 모든원소는 10,000,000 보다 작은 자연수이고 이 값들이 최대 100,000 개 들어갈 수 있다. 따라서 최악의 경우 약 10,000,000 * 100,000 = 10^12 가 나올 수도 있으므로 long long을 써야 한다.