[백준OJ] 7795번 먹을 것인가 먹힐 것인가

https://www.acmicpc.net/problem/7795

7795번: 먹을 것인가 먹힐 것인가

---

풀이

B의 원소들을 정렬한 뒤, LowerBound를 통해 A의 각 원소보다 작은 B의 원소의 개수를 구해주는 방법을 선택함

 

시간 복잡도

정렬은 O(NLogN)

LowerBound는 O(LogN)이 되므로, 시간복잡도는 O(NLogN)이 된다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    //O(LogN)
    public static int lowerBound(int[] list, int target){
        int left = 0;
        int right = list.length-1;

        while(left<=right){
            int middle = (left+right)/2;

            if(list[middle]<target){
                left++;
            }
            else{
                right--;
            }
        }
        return left;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.valueOf(br.readLine());

        for(int tt=0;tt<t;tt++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.valueOf(st.nextToken());
            int m = Integer.valueOf(st.nextToken());

            int[] A = new int[n];
            int[] B = new int[m];

            //O(N)
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<n;i++){
                A[i]=Integer.valueOf(st.nextToken());
            }
            //O(M)
            st = new StringTokenizer(br.readLine());
            for(int i=0;i<m;i++){
                B[i]=Integer.valueOf(st.nextToken());
            }

            //O(MLogM)
            Arrays.sort(B);
            int answer = 0;
            //O(N)
            for(int i=0;i<n;i++){
                answer+=lowerBound(B,A[i]);
            }
            System.out.println(answer);
        }
    }
}