백준 7795번) 먹을 것인가 먹힐 것인가(JAVA)

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

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보다 큰 쌍이 몇 개나 있는지 구하는 프로그램을 작성하시오.

 

#알고리즘

정렬

이분탐색

두 포인터

 

#난이도

Silver 3

 

#풀이방법

문제 자체는 어렵지 않지만 누구도 보다 빠르게 남들과는 다르게(?)  탐색하여 개수를 세어야 하는 것이  포인트이다.

따라서 A와 B를 2개 다 입력 받아 오름차순으로 정렬한 후, 투 포인터를 이용하여 빠른 시간 안에 효율적으로 개수를 세주었다. 

 

int Ap = 0;
            int Bp = 0;
            //집합 A와 B의 초기 위치
            
            int eat_num = 0;//먹은 횟수
            
            while(Ap < A.length) {
        
                if(Bp == B.length) {
                    eat_num += Bp;
                    Ap++;
                    continue;
                }//B가 끝에 도달했으면 다 먹을 수 있으므로 더해주고 다음 것으로 넘어감
                
                if(A[Ap] > B[Bp]) {
                    Bp++;
                }//잡아 먹히는 경우
                else {                    
                    Ap++;
                    eat_num += Bp;
                }//못먹는 경우,이전의 것들을 먹을 수 있으므로 더해주고 다음 것으로 넘어감
                
            }
            
            an[i] = eat_num;

 

 

 

코드를 보면 직관적으로 잘 이해가 되지 않을 수 있는데 테케 예제를 들어 설명하겠다.

 

 

A -> 1 1 3 7 8 (정렬 후)

B -> 1 3 6 (정렬 후)

 

A의 배열과 B의 배열을 정렬 한 후 각 자리를 비교하여,  A가 클 경우 B의 자릿수를 늘려주고,

그렇지 않는 경우 B의 자릿수를 더한 후 A 집합의 다음 원소로 넘어가 B와 비교를 한다.

 

만약 Bp가 끝에 도달했는데 Ap가 아직 끝에 도달하지 않는 경우,  남아있는 AP가 모든 B 집합의 원소를 잡아먹을 수 있으므로, Bp를 더해주고 A집합의 다음 원소로 끝에 도달할때까지 진행한다.

 

 

#전체 코드

import java.util.*;
//1t
 
public class Main {
 
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int T = sc.nextInt();
        int[] an = new int[T];
        
        for(int i=0; i<T; i++) {
            
            int A_size = sc.nextInt();
            int B_size = sc.nextInt();
            
            int[] A = new int[A_size];
            int[] B = new int[B_size];
            
            for(int j=0; j<A.length; j++)
                A[j] = sc.nextInt();
        
            for(int j=0; j<B.length; j++)
                B[j] = sc.nextInt();
            
            Arrays.sort(A);
            Arrays.sort(B);
            //A,B 오름차순 정렬
            
            int Ap = 0;
            int Bp = 0;
            //집합 A와 B의 초기 위치
            
            int eat_num = 0;//먹은 횟수
            
            while(Ap < A.length) {
        
                if(Bp == B.length) {
                    eat_num += Bp;
                    Ap++;
                    continue;
                }//B가 끝에 도달했으면 다 먹을 수 있으므로 더해주고 다음 것으로 넘어감
                
                if(A[Ap] > B[Bp]) {
                    Bp++;
                }//잡아 먹히는 경우
                else {                    
                    Ap++;
                    eat_num += Bp;
                }//못먹는 경우,이전의 것들을 먹을 수 있으므로 더해주고 다음 것으로 넘어감
                
            }
            
            an[i] = eat_num;
            
        }
        
        for(int i=0; i<an.length; i++)
            System.out.println(an[i]);
        
    }
    
    
 
}