EunSung.log

숫자 게임

3 min read

문제 정보

풀이

B팀의 승점이 최대가 되도록 하려면 A의 카드를 이길 때 최대한 작은 값으로 이기는 것이 유리하다. 큰 카드는 아껴뒀다가 더 큰 상대 카드를 이기는 데 써야 하기 때문이다.

이를 위해 양쪽을 정렬한 뒤, A의 큰 값부터 순서대로 B의 카드와 비교한다.

  1. A, B 모두 내림차순으로 순회
  2. B의 현재 카드가 A의 현재 카드보다 크면, 이길 수 있으므로 B 카드를 사용해 승점을 획득한다.
  3. B의 현재 카드가 A의 현재 카드 이하면, 이길 수 없으므로 B 카드를 사용하지 않는다.

여기서 내림차순으로 순회한다는 것이 중요하다.

큰 값부터 비교하면, 지금 B가 이길 수 없는 A의 카드는 포기하고 B 카드를 아낄 수 있다.

현재 B의 카드는 내림차순 순회이므로, 아직 사용하지 않은 B의 카드 중 최대값이다. 즉, 현재 B의 카드가 못 이기면 어쨌든 해당 카드는 못 이기므로 포기하는 것이다.

또한 현재 B의 최대 카드 말고, 더 작은 B 카드로 이기면 안되냐는 의문이 들 수 있다. 하지만 어차피 승점을 얻는다는 결과는 같으므로 상관없다.

앞서 말했듯, 내림차순 순회이므로 A 카드와 B 카드는 그 시점에서 각각의 최대값이다. 즉, B에서 최대가 아닌데 현재 A의 카드를 이길 수 있다는 것은 A의 다른 숫자 또한 이길 수 있다는 뜻이다.

예를 들어, A의 현재 카드는 5, B의 현재 카드는 7인데, B의 카드 중 6이 있는 경우다. A의 남은 카드는 모두 5 이하의 값이므로 현재 A의 카드(5)를 7로 이기든 6으로 이기든 상관없는 것이다.

코드

import java.util.*;
 
class Solution {
    public int solution(int[] A, int[] B) {
        int answer = 0;
        
        Arrays.sort(A);
        Arrays.sort(B);
        
        int idx = B.length - 1;
        
        for(int i = A.length - 1; i >= 0; i--) {
            if (A[i] < B[idx]) {
                answer++;
                idx--;
            }
        }
        
        return answer;
    }
}

백링크