문제

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

---

입력

A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B

---

출력

B 팀원들이 얻을 수 있는 최대 승점

---

풀이

제한조건

• A와 B의 길이는 같습니다.
• A와 B의 길이는 1 이상 100,000 이하입니다.
• A와 B의 각 원소는 1 이상 1,000,000,000 이하의 자연수입니다.

접근방법

정렬문제인것 같다.
배열의 길이가 100,000 이하 이므로, 반복문 2개를 이용하여 검사한다면
1초에 대략 1억번의 연산이 가능하므로 시간초과를 받을 확률이 높다.

정렬을 통해서 해결해보자.

단순하게 생각하면 아래와 같이 승리패턴을 가질 수 있다.

- 승리 : 상대 선수보다 점수가 높으면서, 점수차가 가장 낮은 팀원
- 패배 : 상대 선수보다 점수가 낮으면서, 점수차가 가장 큰 팀원

따라서 A의 팀원 중 가장 점수가 높은 선수를 한명 정하고,
B의 팀원 중에서 가장 점수가 높은 선수와 비교를 하고
이길 수 있다면 그대로 출전, 진다면, 가장 점수가 낮은 선수가 출전하는 방식으로 진행하면 된다.

A의 팀원 중 가장 점수가 높은 선수를 가져오는 이유

• 남은 A팀에서 해당 점수보다 더 높은 선수를 가진 사람이 없다는 것을 보장하기 위해

---

코드

import java.util.*;

class Solution {
    public int solution(int[] A, int[] B) {
    	// 점수 역순으로 pq에 넣는다.
        PriorityQueue<Integer> pq = new PriorityQueue(Collections.reverseOrder());
        for(int i : A)
            pq.add(i);
        
        // 점수순으로 정렬하여 Deque에 삽입
        Arrays.sort(B);
        ArrayDeque<Integer> dq = new ArrayDeque();
        for(int i : B)
            dq.add(i);
        
        int answer = 0;
        while(!pq.isEmpty()){
            int target = pq.poll();
            // B팀의 최고 숫자가 A팀의 최고 숫자보다 높은 경우 승리
            if(target < dq.peekLast()){
                dq.pollLast();
                answer++;
            }else{ // 질때는 가장 작은 숫자를 내며 져야 한다.
                dq.pollFirst();
            }
        }
        
        return answer;
    }
}