[DAY82] Algorithm : Numbers Game

B팀이 A팀의 출전 순서를 보고 승점을 최대로 얻는 방법을 찾는 문제다. 핵심은 "이길 수 있으면 가장 근소한 차이로 이기고, 이길 수 없으면 가장 작은 패를 버리는 것"이다. $N$이 최대 10만이라 $O(N^2)$ 탐색은 불가능하며, 정렬(Sorting)과 투 포인터를 활용한 그리디(Greedy) 알고리즘으로 $O(N \log N)$에 해결해야 한다.

---

❓ 문제 분석

• 목표: A팀의 출전 순서가 고정된 상태에서, B팀의 출전 순서를 조절해 얻을 수 있는 최대 승점 구하기.
• 제약 조건: A, B의 길이는 최대 100,000이다.
  • $O(N^2)$ 알고리즘을 짜면 시간 초과(Time Limit Exceeded)가 발생한다.
  • 최소 $O(N \log N)$ 혹은 $O(N)$으로 해결해야 한다.
• 핵심 키워드: "최대 승점", "자연수", "무작위 배정 후 공개".

---

💡 풀이 설계

1. 시도했던 접근 (First Attempt)

• 처음엔 단순히 A의 각 숫자에 대해 B의 모든 숫자를 순회하며 이길 수 있는 가장 작은 수를 찾으려 했다.
• 혹은, vector의 erase 함수를 써서 사용한 카드를 지우는 방식을 떠올렸다.
• 하지만 배열 중간 요소를 삭제하는 건 $O(N)$의 비용이 들고, 이를 N번 반복하면 전체 복잡도가 $O(N^2)$가 되어 효율성 테스트를 통과할 수 없다고 판단했다.

2. 최종 해결책 (Solution)

• 직관적으로 생각해보면, "현재 내가 가진 가장 센 카드로도 못 이기는 상대라면, 가장 약한 카드를 버리는 게 이득"이다.
• 이를 구현하기 위해 정렬과 투 포인터를 사용했다.
• 예상 시간 복잡도: $O(N \log N)$ (정렬 비용이 지배적임)
• 알고리즘 흐름:
  1. A와 B를 모두 내림차순 정렬한다. (강한 상대를 기준으로 판단하기 위함)
  2. A의 카드를 순서대로(i) 확인한다.
  3. 만약 B의 가장 강한 카드(head)가 A의 카드(i)보다 크다면? $\rightarrow$ 승리! 승점 챙기고 head 인덱스 증가.
  4. 만약 이길 수 없다면? $\rightarrow$ 어차피 질 판이다. 가장 약한 카드(tail)를 소모해서 강한 카드를 아낀다.

---

💻 코드 구현

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(vector<int> A, vector<int> B) {
    int answer = 0;
    int n = A.size();
    int m = B.size();
    
    // 투 포인터 초기화: 
    // head는 현재 B팀의 가장 큰 카드, tail은 가장 작은 카드를 가리킴
    int head = 0, tail = m - 1;

    // 내림차순 정렬
    // 큰 수부터 비교해야 '도저히 못 이기는 상황'을 빠르게 판단 가능
    sort(A.rbegin(), A.rend());
    sort(B.rbegin(), B.rend());

    // A팀의 카드 순회
    for (int i = 0; i < n; i++) {
        // 더 이상 사용할 카드가 없거나 포인터가 교차되면 종료 (방어 코드)
        if (head > tail) break;

        // B의 최강 카드로 A의 현재 카드를 이길 수 있는가?
        if (A[i] < B[head])
        {
            // 이긴다: 승점 획득 후 다음 강한 카드로 이동
            answer++;
            head++;
        }
        else
        {
            // 못 이긴다: 가장 약한 카드(tail)를 버림
            tail--;
        }
    }

    return answer;
}

---

🐛 시행착오 및 디버깅

• 문제점: 배열 요소를 진짜로 삭제하려고 하면 인덱스 관리가 복잡해지고 속도가 느려진다.
• 해결: vector를 수정하지 않고, 인덱스(head, tail)만 조절하여 논리적으로만 카드를 제거했다. 이렇게 하니 시간 복잡도 문제도 해결되고 코드도 훨씬 깔끔해졌다.
• 주의할 점: sort를 할 때 A도 같이 정렬해도 되는지 헷갈렸는데, 어차피 B는 A의 '어떤 숫자'를 상대하느냐가 중요하지 순서는 중요하지 않다는 점을 깨달았다. 즉, A를 정렬해서 비교해도 최댓값을 구하는 데는 문제가 없다.

---

✅ 오늘의 회고

항목	내용
유형	Greedy (탐욕법)
체감 난이도	하 (문제 이해 후 전략만 세우면 구현은 쉬움)
복잡도	시간: $O(N \log N)$, 공간: $O(1)$
새로 배운 것	sort(v.rbegin(), v.rend())로 내림차순 정렬하기, 투 포인터로 삭제 연산 대체하기