[BOJ/Java] 백준 7795번 - 먹을 것인가 먹힐 것인가

백준 #7795 먹을 것인가 먹힐것인가

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

 

import java.io.BufferedReader;
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 {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.parseInt(st.nextToken());
		for (int t = 1; t <= T; t++) {
			// 입력
			st = new StringTokenizer(br.readLine());
			int Ano = Integer.parseInt(st.nextToken());  // A 수
			int Bno = Integer.parseInt(st.nextToken());  // B 수
			
			int[] A = new int[Ano];
			int[] B = new int[Bno];
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < A.length; i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine());
			for (int i = 0; i < B.length; i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			
			// 정렬
			Arrays.sort(A);
			Arrays.sort(B);
			
			// 투포인터
			int i = 0;  // A 인덱스
			int j = 0;  // B 인덱스
			int cnt = 0;  // 큰 쌍의 개수
			while (true) {
				if (i == Ano || j == Bno) break;
				if (A[i] > B[j]) {
					cnt += Ano - i;
					j++;
				} else {
					i++;
				}
			}
			System.out.println(cnt);
		}
		
	}
}

투포인터를 활용해서 풀었다. A 배열과 B 배열을 정렬한 후 앞부터 차근차근 탐색해나가는데, B에서 현재 가리키고 있는 생명체가 A가 가리키고 있는 생명체보다 작을 경우, A가 가리키고 있는 생명체 이후 모든 생명체가 B 생명체를 먹을 수 있는 것을 의미한다. 따라서 A 배열 크기 - A 인덱스가 B를 먹을 수 있는 쌍의 개수가 된다. 쌍의 개수를 합해준 후 다음 B 생명체를 보기 위해 B 인덱스를 +1 해준다. 만약 B 생명체가 A 생명체보다 클 경우, 다음 A 생명체를 보기 위해 A 인덱스를 +1 해준다. 이렇게 구한 쌍의 개수들을 다 합하여 출력해준다.