[백준] 7795. 먹을 것인가 먹힐 것인가 (Java)

 

문제

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

 

알고리즘

투 포인터

 

풀이

1. A와 B를 오름차순 정렬한다.

2. A의 포인터와 B의 포인터를 0으로 초기화한다. (첫 번째 원소부터 비교)

3. A의 포인터의 원소와 B의 포인터의 원소를 비교한다.

    3-1. B의 원소가 더 크거나 같다면 A의 포인터를 1 증가시킨다.

    3-2. A의 원소가 더 크다면 그 이후 수는 전부 B의 원소를 먹을 수 있는 수이므로 그만큼 sum에 더하고, B의 포인터를 1 증가시킨다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		int T = Integer.parseInt(br.readLine());
		for(int t=0;t<T; t++) {
			ArrayList<Integer> A = new ArrayList<>();
			ArrayList<Integer> B = new ArrayList<>();

			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());

			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; i++)
				A.add(Integer.parseInt(st.nextToken()));

			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < M; i++)
				B.add(Integer.parseInt(st.nextToken()));

			Collections.sort(A);
			Collections.sort(B);

			int aIndex = 0;
			int bIndex = 0;

			int sum = 0;
			while (aIndex < N && bIndex < M) {
				if (A.get(aIndex) > B.get(bIndex)) {
					sum += N - aIndex;
					bIndex++;
				}

				else
					aIndex++;
			}

			sb.append(sum).append("\n");
		}
		
		System.out.println(sb);
	}
}