두 카드

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


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 N = Integer.parseInt(st.nextToken()); // 1 ~ 10만 이하
        int M = Integer.parseInt(st.nextToken()); // 1 ~ 100 이하

        st = new StringTokenizer(br.readLine());
        int[] cards = new int[N];
        for(int i = 0; i < N; i ++){
            cards[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        int[] winningNumbers = new int[M];
        for(int i = 0; i < M; i ++){
            winningNumbers[i] = Integer.parseInt(st.nextToken());
        }

        int answer = findTheNumberOfWinningNumbers(cards, winningNumbers);
        System.out.println(answer);
    }

    static int[] sorted;
    private static int findTheNumberOfWinningNumbers(int[] cards, int[] winningNumbers) {
        int cnt = 0;
        sort(cards);
        for(int winningNumber : winningNumbers){
            for(int card : cards){
                int a = winningNumber - card;
                if(binarySearch(cards, a)){
                    cnt ++;
                    break;
                }
            }
        }
        return cnt;
    }

    private static boolean binarySearch(int[] cards, int key) {
        int lo = 0;
        int ro = cards.length - 1;
        int mid;

        while(lo <= ro){
            mid = (lo + ro) / 2;

            if(key == cards[mid]){
                return true;
            }
            else if(key < cards[mid]){
                ro = mid - 1;
            }
            else{
                lo = mid + 1;
            }
        }

        return false;
    }

    private static void sort(int[] cards) {
        sorted = new int[cards.length];
        mergeSort(cards, 0, cards.length - 1);
        sorted = null;
    }

    private static void mergeSort(int[] cards, int lo, int ro) {
        if(lo == ro) return;
        int mid = (lo + ro) / 2;

        mergeSort(cards, lo, mid);
        mergeSort(cards, mid + 1, ro);

        merge(cards, lo, mid, ro);
    }

    private static void merge(int[] cards, int lo, int mid, int ro) {
        int left = lo;
        int right = mid + 1;
        int idx = lo;
        while(left <= mid && right <= ro){
            if(cards[left] > cards[right]){
                sorted[idx] = cards[right];
                idx++;
                right ++;
            }
            else{
                sorted[idx] = cards[left];
                idx++;
                left ++;
            }
        }
        if(left > mid){
            while(right <= ro){
                sorted[idx] = cards[right];
                right ++;
                idx ++;
            }
        }
        else{
            while(left <= mid){
                sorted[idx] = cards[left];
                left ++;
                idx ++;
            }
        }

        for(int i = lo; i <= ro; i ++){
            cards[i] = sorted[i];
        }
    }
}

문제 풀이

1. a + b = c에서 a와 c의 숫자를 알고 있다고 가정하면 b = a - c 공식이 성립한다. 그래서 이진 탐색 이용해서 해결하려면 먼저 정렬이 필요했다. (합병 정렬을 직접 구현해서 진행하였다 - 익숙해지기 위해서)

2. 그 다음 cards 배열 안에 있는 값 중에 b가 존재한다면 true, 존재하지 않는다면 false를 리턴해주는 이진 탐색도 직접 구현해서 만약 존재하면 2번째 for문을 나가게 되고, 아니라면 계속 돌아 false를 리턴하게 된다.