풀이
A팀의 카드를 보고 B팀이 최대로 이길 수 있는 점수를 구하려면 효율적으로 카드를 분배하는 것이 중요히다
•
최대한 승리하면서 상대팀의 높은 숫자를 없애고
•
최대한 승리하면서 우리팀의 낮은 숫자를 없애야 한다.
1.
A팀의 숫자카드와 B팀의 숫자카드를 모두 정렬한다.
2.
A팀과 B팀의 숫자카드를 작은 순서대로 하나씩 꺼낸다.
3.
A팀의 숫자카드를 이길 수 있으면서 가장 작은 숫자카드를 구하고 answer 값을 올린다.
4.
어느 팀이던 카드가 소진되면 B팀이 더 이상 이길 수 없고 그때의 answer가 B팀이 이기는 최댓값이다.
정렬 시간을 줄이기 위해 우선순위큐 자료구조를 사용했다.
import java.util.*;
class Solution {
public int solution(int[] A, int[] B) {
int answer = 0;
Queue<Integer> heap = new PriorityQueue<>();
Queue<Integer> heap2 = new PriorityQueue<>();
for (int i : A) heap.offer(i);
for (int i : B) heap2.offer(i);
while (!heap.isEmpty() && !heap2.isEmpty()) {
int left = heap.poll();
int right = heap2.poll();
while(left >= right){
if (! heap2.isEmpty()){
right = heap2.poll();
}
else
return answer;
}
answer++;
}
return answer;
}
}
Java
복사