[HackerRank] Permuting Two Arrays

2주차 자료구조 복습
Practice > Algoritms > Greedy

풀이

A 배열의 아이템과 B 배열의 아이템의 합이 모두 k 이상이 되어야 한다. 이때 각 배열을 정렬한 후 한 배열에서는 최대값을, 다른 배열에서는 최소값을 꺼내어 더하면 모두 k 이상이 될 확률이 높아진다. 따라서 A 배열은 내림차순으로, B 배열은 오름차순으로 정렬한 뒤 두 값을 더한 값이 k보다 작다면 문제의 조건을 통과하지 못하기 때문에 바로 "NO"를 반환하였다. for문이 모두 종료된다면 모두 k 이상이라는 것이므로 "YES"를 반환하였다.

전체적인 코드는 다음과 같다.

string twoArrays(int k, vector<int> A, vector<int> B) {
    vector<int> temp;
    sort(A.begin(), A.end(), greater<int>()), sort(B.begin(), B.end());
    for(int i=0; i<A.size(); i++){
        if(A[i] + B[i] < k)
            return "NO";
    }
    return "YES";
}

모든 테스트 케이스를 맞춘 모습을 볼 수 있다.