[Java] 세 카드 알고리즘

1. 문제

카드 개수 n개가 있고, 정답 카드 m개가 있다
n개의 카드 개수중 3개를 뽑아 세 카드의 합이 m이 되는 값을 도출하고자 한다
(단, 하나의 같은 카드를 중복으로 뽑는게 가능)
3개의 카드를 뽑아 가능한 정답카드를 오름차순으로 출력하시오

입력 형식

첫 줄에는 카드의 갯수 n (1 ~ 1000) 정답 카드의 수 m(1 ~ 100)을 입력한다
두 번째 줄에는 N개의 카드에 적힌 숫자들이 주어진다(1 ~ 1억이하의 자연수)
세 번째 줄에는 M개의 당첨번호가 주어진다(1 ~ 2억이하의 자연수)

출력 형식

M개의 당첨번호 들 중 실제로 세 카드에 적힌 숫자의 합으로 표현될 수 있는 당첨번호들을 모두 출력한다.

실제로 만들 수 있는 당첨번호가 여러개라면, 오름차순으로 정렬하고 각 숫자는 공백으로 구분하여 한 줄에 출력한다.
실제로 만들 수 있는 당첨번호가 존재하지 않는다면 NO를 출력

2. 알고리즘 접근

이 문제는 전에 블로그에 정리한 문제의 변형이므로 구체적인것은 -> 링크 클릭
위 정리한 블로그 링크에서는 조합 -> 탐색으로 변형하여 풀었다면
이 문제는 조합 + 탐색을 이용한 풀이를 하면된다(n값이 바꼈기 때문)

3. 알고리즘 풀이

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Q3I {
    static final Scanner sc = new Scanner(System.in);
    private static ArrayList<Integer> getPossibleTargetNumber(int n, int m, int[] cards, int[] target) {

        Arrays.sort(cards); // 이진 검색을 위한 정렬
        ArrayList<Integer> answers = new ArrayList<Integer>();

        for(int k : target){ // 모든 검사해야할 k에 대해

            boolean possible = false; // k를 세 숫자의 합으로 표현할 수 있는지

            for(int i = 0; i < n; i++){
                int x = cards[i];
                for(int j = 0; j <= i; j++){
                    int y = cards[j];
                    int z = k - (x + y); // z값을 구해 이진검색한다

                    if(Arrays.binarySearch(cards, z) >= 0){
                        possible = true;
                        break;
                    }
                }
                if(possible){
                    // 이미 찾았으면 탈출 (가지치기)
                    break;
                }
            }
            if(possible){
                answers.add(k);
            }
        }
        return answers;
    }

    public static void main(String[] args) {
        int n = sc.nextInt(); // 사용할 카드의 수 (1 ~ 1000)
        int m = sc.nextInt(); // 당첨번호의 수 (1 ~ 100)

        int[] cards = new int[n]; // 카드의 수를 담을 배열
        int[] target = new int[m]; // 당첨 번호의 수를 담을 배열

        for(int i = 0 ; i < n; i++){
            cards[i] = sc.nextInt(); // 카드 데이터 입력
        }
        for(int i = 0; i < m; i++){
            target[i] = sc.nextInt(); // 당첨 데이터 입력
        }

        ArrayList<Integer> answers = getPossibleTargetNumber(n, m, cards, target);

        if(answers.size() == 0){
            System.out.println("NO");
        }else{
            for(int i = 0; i < answers.size(); i++){
                if(i > 0){
                    System.out.print(" ");
                }
                System.out.print(answers.get(i));
            }
        }

    }
}

조합과 탐색을 복습할 수 있는 시간이었다 :)