Problem | 먹을 것인가 먹힐 것인가
심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.
두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.
이분 탐색 : 정렬의 특성을 이용한 탐색
A의 사이즈와 B의 사이즈만큼 돌면서 작은 수를 count 해준다.
시간복잡도 O(n^2)
Example ) A=[8,1,7,3] B=[3,6,1]
static int BinarySearch(int[] B,int L,int R,int a) {
int arrow=L-1;
while(L<=R) {
int mid=(L+R)/2;
if(B[mid]<a) {
arrow=mid;
L=mid+1;
}
else
R=mid-1;
}
//System.out.println(arrow);
return arrow;
}
static void pro() {
int ans=0;
/*1. B배열 정리하기*/
Arrays.sort(B,1,M+1);
/*2. 몇 번째부터 count인지 체크*/
for(int i=1;i<=N;i++)
ans+=BinarySearch(B,1,M,A[i]);
System.out.println(ans);
}
import java.util.Arrays;
import java.util.Scanner;
/*백준 7795 먹을 것인가 먹힐 것인가
* Date . 2021.09.13
* Using. 기초 이분탐색
*/
public class Main {
static int N,M;
static int[] A,B;
//@SuppressWarnings("resource")
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int T;
T=sc.nextInt();
for(int i=0;i<T;i++) {
N=sc.nextInt();
M=sc.nextInt();
/*A,B 배열 값 설정 후 입력받기*/
A=new int[N+1];
B=new int [M+1];
for(int a=1;a<=N;a++)
A[a]=sc.nextInt();
for(int b=1;b<=M;b++)
B[b]=sc.nextInt();
pro();
}
}
static void pro() {
int ans=0;
/*1. B배열 정리하기*/
Arrays.sort(B,1,M+1);
/*2. 몇 번째부터 count인지 체크*/
for(int i=1;i<=N;i++)
ans+=BinarySearch(B,1,M,A[i]);
System.out.println(ans);
}
static int BinarySearch(int[] B,int L,int R,int a) {
int arrow=L-1;
while(L<=R) {
int mid=(L+R)/2;
if(B[mid]<a) {
arrow=mid;
L=mid+1;
}
else
R=mid-1;
}
//System.out.println(arrow);
return arrow;
}
}
💡배열의 크기를 입력받은 것보다 +1 해줬다.
즉, B[0]부터 값이 들어오는 것이 아닌, B[1]부터 시작해준다.