[프로그래머스] 숫자게임 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다.

• 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다.
• 각 사원은 딱 한 번씩 경기를 합니다.
• 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다.
• 만약 숫자가 같다면 누구도 승점을 얻지 않습니다.

전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로 팀원들의 출전 순서를 정했습니다. 이때의 B팀이 얻는 승점을 구해주세요.
A 팀원들이 부여받은 수가 출전 순서대로 나열되어있는 배열 A와 i번째 원소가 B팀의 i번 팀원이 부여받은 수를 의미하는 배열 B가 주어질 때, B 팀원들이 얻을 수 있는 최대 승점을 return 하도록 solution 함수를 완성해주세요.

2. 입력

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

3. 예제

A	B	result
[5,1,3,7]	[2,2,6,8]	3
[2,2,2,2]	[1,1,1,1]	0

4. 풀이

B팀이 최대한 승점을 얻으려면 A팀의 숫자를 이길 수 있는 숫자들 중 가장 큰 값들과 게임을 진행해야 B팀이 최종적으로 많은 승리를 가져갈 수 있습니다.

 

예제 1번에서 B팀에서 가장 큰 수인 8은 A팀의 어떤 수와 게임을 하여도 승리 할 수 있습니다.

하지만 7이 아닌 다른 수와 게임을 진행한다면 최대 승리 횟수가 달라지게 됩니다.

 

A팀의 숫자들 중 숫자 8로 이길 수 있는 수들 중 가장 큰 숫자 7과 경기를 한 경우는 최대 승리 횟수가 3회 입니다.

 

하지만 A팀의 숫자들 중 숫자 8로 이길 수 있는 수들 중 2번째 큰 수 5와 게임을 한 경우는 최대 승리 횟수가 2회 입니다.

 

그러므로 A와 B모두 내림차순으로 숫자 카드를 정렬한 뒤 A팀의 카드를 한장씩 꺼내어 B팀의 최대 값과 비교를 진행 합니다.

 

A팀의 가장 큰 값 7과 B팀의 가장 큰 값 8을 비교하면 B팀의 카드가 더 크므로 게임을 진행 합니다. 게임을 진행 하였으므로 A팀과 B팀의 카드는 각각 제거 됩니다.

 

A팀의 가장 큰 값 5와 B팀의 가장 큰 값 6을 비교하면 B팀의 카드가 더 크므로 게임을 진행 합니다. 게임을 진행 하였으므로 A팀과 B팀의 카드는 각각 제거 됩니다.

 

A팀의 가장 큰 값 3와 B팀의 가장 큰 값 2을 비교하면 A팀의 카드가 더 크므로 A팀의 카드를 패스 합니다.

패스하는 경우는 결국 B팀의 최소 카드를 내는 것과 같은 것이므로 최소 값을 제거하는 과정을 줄이기 위해 A팀의 카드만 제거 합니다.

 

A팀의 가장 큰 값 1와 B팀의 가장 큰 값 2을 비교하면 B팀의 카드가 더 크므로 게임을 진행 합니다. 게임을 진행 하였으므로 A팀과 B팀의 카드는 각각 제거 됩니다.

 

그럼 최종적으로 승리 횟수가 3으로 최대 3게임을 이길 수 있습니다.

 

5. 코드

전체 코드는 Git에 있습니다.

PriorityQueue<Integer> aQueue = new PriorityQueue<>(Comparator.reverseOrder());
PriorityQueue<Integer> bQueue = new PriorityQueue<>(Comparator.reverseOrder());

for (int i = 0; i < A.length; i++) {
	aQueue.offer(A[i]);
	bQueue.offer(B[i]);
}

int answer = 0;
while (!aQueue.isEmpty()) {
	int aNum = aQueue.poll();
	int bNum = bQueue.peek();

	if (aNum < bNum) {
		bQueue.poll();
		answer++;
	}
}

return answer;