백준 7795번: 먹을 것인가 먹힐 것인가 [이분탐색][정렬] - Java

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

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

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());

		int T = Integer.parseInt(st.nextToken());

		for (int tc = 0; tc < T; tc++) {
			//입력
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			int arrA[] = new int[A];
			int arrB[] = new int[B];

			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < A; i++) {
				arrA[i] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arrA);
			
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < B; i++) {
				arrB[i] = Integer.parseInt(st.nextToken());
			}
			Arrays.sort(arrB);
			
			//A기준으로 B를 이분탐색 (매개변수 탐색)
			
			int res = 0;

			for (int i = 0; i < A; i++) {
				
				int s = 0;
				int e = B-1;
				
				int ans = -1;
				
				while(s<=e) {
					
					int mid = (s+e)/2;
					
					if( arrA[i] <= arrB[mid] ) {
						e = mid - 1;
					} else {
						s = mid+1;
						ans = mid;
					}
					
				}
//				System.out.println("ans : "+ans);
				res += ans+1;
				
			}
			
			System.out.println(res);
			
		}

	}

}

 

투 포인터도 활용할 수있다.

정렬을 했기때문에 A[i]에서 B[j+2]까지 먹었다면 A[i+1]은 B[j+2]은 무조건 먹을거니 B[j+3]만 봐도되는법..