문제

풀이

1. 이분탐색
   • B 배열만 정렬해주고 A 배열 각 원소마다 이분탐색 진행
2. 원포인터
   • A,B 둘다 정렬 원포인터 사용
   • a[i] 원소보다 큰거나 같은 것 발견할때까지 포인터 이동, 멈추면 다음 원소로 포인터부터 시작해서 다시 진행

코드

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
//        System.out.println(new Solution().solution(elements));
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

        int t=Integer.parseInt(br.readLine());
        while(t-->0){
            StringTokenizer st=new StringTokenizer(br.readLine());
            int n=Integer.parseInt(st.nextToken());
            int m=Integer.parseInt(st.nextToken());
            int[] a=new int[n];
            int[] b=new int[m];

            st=new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++)a[i]=Integer.parseInt(st.nextToken());
            st=new StringTokenizer(br.readLine());
            for(int i=0;i<m;i++)b[i]=Integer.parseInt(st.nextToken());
            Arrays.sort(b);
			
            //이분탐색
            int ans=0;
            for(int num:a){
                int l=0;
                int r=m-1;
                int mid=(l+r)/2;
                while(l<=r){
                    mid=(l+r)/2;
                    if(num<=b[mid]){
                        r=mid-1;
                    }
                    else if(num>b[mid]){
                        l=mid+1;
                    }
                }
                ans+=l;
            }

				// 원포인터
//            Arrays.sort(a);
//            int ans=0,pointer=0;
//            for(int num:a){
//                while( pointer<m && num>b[pointer]){
//                    pointer++;
//                }
//                ans+=pointer;
//            }
            System.out.println(ans);
        }
    }
}

#이분탐색