세 카드

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 ~ 1000 이하
        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());
        }
        sort(cards); // nlogN
        sort(winningNumbers); // nlogN
        Set<Integer> set = new LinkedHashSet<>();
        for(int i = 0; i < N; i ++){
            for(int j = 0; j < N; j ++){
                for(int k = 0; k < M; k++){ // 최대 1억
                    int find = winningNumbers[k] - (cards[i] + cards[j]);
                    if(find < 0) continue;
                    if(binarySearch(find, cards)){
                        set.add(winningNumbers[k]);
                    }
                }
            }
        }
        if(set.isEmpty()) System.out.println("NO");
        else{
            List<Integer> list = new ArrayList<>(set);
            Collections.sort(list);
            list.forEach(s -> System.out.print(s + " "));
        }
    }

    private static boolean binarySearch(int key, int[] cards) {
        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;
    }

    static int[] sorted;
    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, ro);
    }

    private static void merge(int[] cards, int lo, int ro) {
        int left = lo;
        int mid = (lo + ro) / 2;
        int right = mid + 1;
        int idx = lo;

        while(left <= mid && right <= ro){
            if(cards[left] > cards[right]){
                sorted[idx] = cards[right];
                right ++;
            }
            else{
                sorted[idx] = cards[left];
                left ++;
            }
            idx ++;
        }

        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 = d -> c = d - a - b 이 공식을 사용해서 풀면 되고 이게 가능한 것은 N이 10만이하에서 1000 이하로 조건이 변경되었기 때문에 3중 for문이 1억건 이하로 돌아가게된다.

2. 나머지 정렬과 이진탐색은 익숙해지기 위해서 구현을 해서 풀었다