숫자 게임

문제

A팀과 B팀이 자연수가 적힌 카드를 내며 게임을 합니다. 규칙은 각 팀의 카드를 한 장씩 내어 숫자를 비교하고, 숫자가 더 큰 쪽이 1점을 얻는 방식입니다. (숫자가 같거나 작으면 점수를 얻지 못합니다.) A팀이 낼 카드의 순서가 미리 주어졌을 때, B팀의 카드 배열을 적절히 재배치하여 B팀이 얻을 수 있는 최대 승점을 구하는 프로그램을 작성하는 문제입니다.

• 입력: A팀의 카드 배열 A, B팀의 카드 배열 B (각 배열의 길이는 1 이상 100,000 이하, 원소는 1,000,000,000 이하의 자연수)
• 출력: B팀이 얻을 수 있는 최대 승점

링크: https://school.programmers.co.kr/learn/courses/30/lessons/12987

풀이: 정렬과 탐욕법(Greedy)을 활용한 매칭

A팀의 가장 큰 숫자를 이기기 위해서는 B팀도 자신이 가진 가장 큰 카드 중 하나를 내야 합니다. 만약 B팀의 가장 큰 카드로도 A팀의 카드를 이길 수 없다면, 해당 라운드는 어차피 이길 수 없으므로 B팀의 가장 작은 카드를 내어 희생시키는 것이 이득입니다. 이러한 논리로 접근하는 전형적인 탐욕법 풀이입니다.

• 오름차순 정렬: 두 배열 A와 B를 모두 오름차순으로 정렬합니다. 이를 통해 가장 큰 카드부터 차례대로 비교할 수 있는 상태를 만듭니다.
• 투 포인터 탐색: 배열의 끝(가장 큰 숫자)부터 역순으로 순회합니다. i는 A팀 카드의 인덱스이고, idx는 B팀 카드의 인덱스입니다.
• 승리 조건 판별: * B[idx] > A[i]: B팀의 현재 가장 큰 카드로 A팀의 카드를 이길 수 있는 경우입니다. 승점(ans)을 1 증가시키고, 다음으로 큰 B팀 카드를 확인하기 위해 idx를 감소시킵니다.
  • B[idx] <= A[i]: B팀의 가장 큰 카드로도 A팀의 카드를 이길 수 없는 경우입니다. 이 경우 B팀은 이길 수 없는 A팀 카드에 작은 카드를 버렸다고 간주합니다. (코드 상에서는 idx를 감소시키지 않고 유지한 채, 다음으로 작은 A팀 카드를 비교 대상으로 넘기게 됩니다.)

코드

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int ans = 0;
        
        // 두 배열을 오름차순으로 정렬
        Arrays.sort(A);
        Arrays.sort(B);
        
        int idx = B.length - 1;
        
        // 가장 큰 숫자부터 역순으로 비교
        for (int i = A.length - 1; i >= 0; i--) {
            // B팀의 카드가 A팀의 카드보다 커서 이길 수 있는 경우
            if (A[i] < B[idx]) {
                ans++;
                idx--; // B팀의 다음 카드로 넘어감
            }
            // 이길 수 없다면 B팀의 카드는 유지하고(가장 작은 카드를 낸 것으로 간주), 
            // A팀의 다음(더 작은) 카드와 다시 비교함
        }
        
        return ans;
    }
}

알고리즘 분류

정렬 (Sorting), 탐욕법 (Greedy), 투 포인터 (Two Pointers)