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

📚 오늘의 문제

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

---

문제 설명

심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 수 있는 쌍의 개수는 7가지가 있다. 8-3, 8-6, 8-1, 7-3, 7-6, 7-1, 3-1.

두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 A의 수 N과 B의 수 M이 주어진다. 둘째 줄에는 A의 크기가 모두 주어지며, 셋째 줄에는 B의 크기가 모두 주어진다. 크기는 양의 정수이다. (1 ≤ N, M ≤ 20,000) 

출력

각 테스트 케이스마다, A가 B보다 큰 쌍의 개수를 출력한다.

예제 입력 1

2
5 3
8 1 7 3 1
3 6 1
3 4
2 13 7
103 11 290 215

예제 출력 1

7
1

문제 풀이

A = [8, 2, 4, 9, 11]

B = [3, 6, 1, 10, 13]

 

위 테스트 케이스를 생각해보자. A, B를 둘다 오름차순으로 정렬 했을 때 

 

A = [2, 4, 8, 9 ,11]

B = [1, 3, 6, 10, 13]

 

이와 같은 배열이 될 것이다.

A의 마지막 원소부터 첫 원소까지 (큰 값에서 작은 값 방향으로) 반복을 하고 B배열의 인덱스를 투포인터처럼 움직여 answer을 갱신하는 방식으로 접근했다.

 

A -> 11

B = [1, 3, 6, 10 ,13]

currentIndex = 4

 

11보다 작은값을 발견할 때 까지 currentIndex를 감소시킨다.

 

A -> 11

B = [1, 3, 6, 10 ,13]

currentIndex = 3

 

즉 A의 11이라는 원소는 0~3까지의 B의 원소를 먹을 수 있으므로 answer에 4의 값을 더해준다.

값을 더한 후 다음 반복문 실행

 

A -> 9

B = [1, 3, 6, 10 ,13]

currentIndex = 2

 

9보다 작은 값을 찾을 때까지 currentIndex를 감소시킨 후

원소 9는 0~2까지의 B원소를 먹을 수 있으므로 answer에 3의 값을 더해준다.

 

위와 같은 로직을 A의 첫번 째 원소까지 반복하여 answer을 갱신하면 A가 B보다 큰 쌍의 개수를 구할 수 있다.

 

package week10;

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

public class boj7795 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        for(int t = 0; t<T; t++){ //테스트 케이스 개수
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());
            int answer = 0;
            int[] arrN = new int[N];
            int[] arrM = new int[M];
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i<N; i++){//A의 배열 초기화
                arrN[i] = Integer.parseInt(st.nextToken());
            }
            st = new StringTokenizer(br.readLine());
            for(int i = 0; i<M; i++){// B의 배열 초기화
                arrM[i] = Integer.parseInt(st.nextToken());
            }
            Arrays.sort(arrN); //배열 A 오름차순 정렬
            Arrays.sort(arrM); //배열 B 오름차순 정렬
            int MIndex = arrM.length-1; //배열 B의 currentIndex
            for(int i = arrN.length-1; i>=0; i--){ //A의 원소별 먹을 수 있는 B 원소의 개수 구하기.
                while(MIndex!=-1&&arrN[i]<=arrM[MIndex]){ // A 원소보다 작은 B 원소가 나올 때 까지 currentIndex 감소
                    MIndex--;
                }
                answer += MIndex+1; //0 ~ currentIndex, 즉 A 원소가 먹을 수 있는 B 원소의 개수 더해주기.
            }
            System.out.println(answer);
        }
        br.close();
    }
}