Programmers : 숫자 게임

풀이요약

논리적 지식

풀이 상세

1. 임의의 A 값이 주어지고, B 의 카드를 최적화해서 카드를 뽑아야한다. 결국 A가 어떤 순서에 카드를 배치되어있든 B는 그에 맞는 순서로 정렬되어야 한다. 즉, 카드의 순서는 최대 승점에 영향을 미치지 않는다 는 점을 인지해야한다.
2. 그렇다면, 크기 비교를 편하게 하기 위해, A,B 모두 정렬을 진행한 후, B 가 이길 가능성을 구하자.
3. 둘다 가장 작은 카드를 시작으로, B가 큰 경우에 승점을 올리자. 그렇지 않은 경우는 B가 A보다 큰 경우를 찾아야 하므로 A의 현재 카드를 놔둔 체, B의 다음카드를 보자.

배운점

• 반드시 꼭 모든 경우를 탐색해야한다는 점에서 B만 정렬하고, A 카드를 기준으로 이분 탐색과 DFS() 를 함께 사용하여 탐색하였다. 답은 정확히 나오나 시간 초과가 걸리더라
• 특별한 알고리즘 지식보다, 접근이 중요한 문제였다. 이런게 더 어려운 문제인듯 하다.

#include <vector>
#include <algorithm>
using namespace std;
int solve(vector<int> &A, vector<int> &B) {
    int AIdx = 0, BIdx = 0, ans = 0, size = A.size();
    while (BIdx<size) A[AIdx] >= B[BIdx] ? BIdx++ : (AIdx++, BIdx++, ans++);
    return ans;
}

int solution(vector<int> A, vector<int> B) {
    sort(A.begin(), A.end()), sort(B.begin(), B.end());
    return solve(A, B);
}