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

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

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

 

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        for(int i=0;i<t;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int a[] = new int[n];
            int b[] = new int[m];

            //a입력
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<n;j++) {
                a[j] = Integer.parseInt(st.nextToken());
            }
            //b입력
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0;j<m;j++) {
                b[j] = Integer.parseInt(st.nextToken());
            }

            Arrays.sort(b);
            int result = 0;

            for(int j=0;j<n;j++) {
                int start = 0, end = m - 1;
                int max=-1;
                while (start <= end) {
                    int mid = (start + end) / 2;

                    if (a[j]<=b[mid]) end=mid-1;
                    else if (a[j]>b[mid]){
                        if(max<mid) max=mid;
                        start=mid+1;
                    }
                }
                result+=(max+1);
            }
            bw.write(result + "\n");
        }
        bw.flush();
    }
}

 

 

해결방법

일단 배열 B를 정렬하고, 핵심은 배열 A의 값마다  배열 B의 값보다 큰 경우의 인덱스 중 가장 큰 값을 찾아 결괏값에 더해 주었다. 이를 수행할 때 이분 탐색을 사용하였다. 인덱스 중 가장 큰 값+1 은 곧 A가 B를 먹을 수 있는 쌍의 개수가 된다.

 

굳이 이분탐색을 쓰지 않고 배열 A도 정렬하여 뒤에서부터 비교하도록 반복문을 돌려도 답은 맞게 나온다. 코드도 간단해지고 성능도 좋아진다.