문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12987
코딩테스트 연습 - 숫자 게임
xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로
programmers.co.kr
문제 알고리즘 고안
For. 낭비를 최소화
[남아 있는 B의 가장 큰 값]에 [남아 있는 A의 값중 B가 이길 수 있는 가장 큰 값]을 할당 시켜주는 게 중요하다.
풀이 방법
1. 정렬
2. 가장 마지막 값 부터 비교 시작
-> while 모든 탐색을 위해 indexA >= 0 && indexB >= 0 이면 반복 (indexA--, indexB--)
-> while 남아 있는 A값 중 최고값 >= 남아 있는 B값 중 최고값 이면
A는 현재의 B값으론 도저히 이길 수 없으니 indexA--해서 패스
-> 두번째 while문 탈출 후 (남아 있는 A값 중 최고값 < 남아 있는 B값 중 최고값이면)
B가 효율적으로 이길 수 있는 것이니까 answer++ 하고 index는 한칸씩 내림
소스코드
package programmers;
import java.util.Arrays;
public class 숫자게임 {
public int solution(int[] A, int[] B) {
int answer = 0;
int n = A.length;
// 정렬
Arrays.sort(A);
Arrays.sort(B);
int indexA = n - 1;
int indexB = n - 1;
outer: while (indexA >= 0 && indexB >= 0) {
while (A[indexA] >= B[indexB]) {
indexA--;
if (indexA < 0) {
break outer;
}
}
answer++;
indexB--;
indexA--;
}
return answer;
}
}