배열 B를 재배열해 모든 원소 합이 x 이하가 되도록 할 수 있는지 확인하는 C++ 코드

문제 설명

크기가 n인 두 개의 배열 A와 B, 그리고 하나의 정수 x가 주어집니다. 우리가 확인해야 할 것은 배열 B의 원소들을 적절히 재배열했을 때, 모든 인덱스 i(0 ~ n-1)에 대해 A[i] + B[i] ≤ x 조건을 만족할 수 있는지 여부입니다.

예를 들어 입력이 A = [1, 2, 3], B = [1, 1, 2], x = 4라고 가정해 보겠습니다. B를 [1, 2, 1] 형태로 재배열하면 각 위치의 합이 1 + 1 ≤ 4, 2 + 2 ≤ 4, 3 + 1 ≤ 4가 되므로 결과는 참(True)이 됩니다.

접근 방법

이 문제는 그리디(Greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• 배열 A는 오름차순으로, 배열 B는 내림차순으로 정렬합니다.
• 이렇게 하면 A의 작은 값과 B의 큰 값이 서로 대응되어 전체 합이 고르게 분산되므로, 조건을 만족하는 배치가 존재한다면 반드시 이 배치에서 드러납니다.
• 정렬된 상태에서 같은 인덱스끼리 짝지은 합 중 하나라도 x를 초과하면, 어떻게 재배열하더라도 조건을 만족할 수 없으므로 거짓(False)을 반환합니다.
• 모든 쌍의 합이 x 이하라면 참(True)을 반환합니다.

이 방법의 시간 복잡도는 정렬 과정이 지배하므로 O(n log n)입니다.

알고리즘 단계

다음 단계에 따라 문제를 해결합니다.

n := 배열 A의 크기
A를 오름차순으로 정렬
B를 내림차순으로 정렬
i := 0부터 n-1까지 반복:
    sum := A[i] + B[i]
    만약 sum > x 라면:
        ans := 0
ans가 0이 아니면:
    return true
그렇지 않으면:
    return false

구현 예시

아래 구현을 통해 더 자세히 이해해 보겠습니다.

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

bool solve(vector<int> A, vector<int> B, int x){
    int n = A.size();
    int ans = 1;
    int sum = 0;
    // A는 오름차순, B는 내림차순으로 정렬
    sort(A.begin(), A.end());
    sort(B.begin(), B.end(), greater<int>());
    for (int i = 0; i < n; ++i){
        sum = A[i] + B[i];
        if (sum > x)
            ans = 0;
    }
    if (ans)
        return true;
    else
        return false;
}

int main(){
    vector<int> A = { 1, 2, 3 };
    vector<int> B = { 1, 1, 2 };
    int x = 4;
    cout << solve(A, B, x) << endl;
}

입력

{ 1, 2, 3 }, { 1, 1, 2 }, 4

출력

1