[Java] 네 카드 (PS)

세카드 알고리즘 << 이 문제의 변형 문제입니다.

1. 문제 설명

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

입력 형식

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

출력 형식

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

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

2. 알고리즘 설명

4개의 카드를 조합해 그 합이 당첨번호에 있는지 파악필요
조합을 탐색으로 변형하는 알고리즘 -> 두 카드 알고리즘 클릭
4개중 3개를 조합으로 판단하고 1개를 이진검색으로 구해도 시간복잡도는
O($M * N^3 * Log_2N$)의 시간복잡도를 가질 것 -> 불가능

선택 할 카드가 많아져, 반복문으로 세 장의 카드를 선택하는 건 힘들다.

그러나 이 문제는 아래의 조건이 있어 카드를 선택할 조건이 단순해진다

• 모든 카드는 중복해서 선택해도 상관없다
• 카드를 선택함에 있어서 중요한 것은 합

카드를 꼭 한장 한장 뽑아야 할 필요가 있을까?

두 카드의 조합을 하나의 짝으로 생각해 문제를 풀자
ex) 카드 4장 p, q, r, s를 뽑는다고 가정하면
p + q = x
r + s = y 이런식으로 하나의 짝으로 변환하자
x + y = k(목표값)인 값을 찾으면 될 것

즉 두 카드의 짝을 클래스로 정의하여 두 카드의 합으로 비교기준을 정의하면
sort, binary search를 활용할 수 있다.

카드가 n개 있고 두개의 카드로 만들수 있는 짝은 $n^2$
$n^2$개의 카드를 순회하면서 만들고 리스트에 저장하여 구현

효율성 검사

카드 : $n$개 -> 2개의 짝 : $n^2$개
카드의 짝을 정렬한다면 $O(N^2Log_2N^2)$ -> 로그법칙 지수는 계수로 바뀐다
$O(2N^2 Log_2N)$의 시간복잡도를 가지게 됨 n = 1000 이하
200만 log_2N정도의 시간복잡도를 가짐
Log시간 복잡도를 가진다면 n이 제곱배가 된다해도 n배씩 커진다(제곱씩 커지는게아님)

3. 알고리즘 풀이

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Q3J {
    static final Scanner sc = new Scanner(System.in);

    private static ArrayList<Integer> getPossibleTargets(int n, int m, int[] cards, int[] target) {

        // 두개의 카드끼리 짝을 지어 페어의 리스트를 만들고 두개의 페어를 고르는 식으로 문제 변환
        ArrayList<Integer> possibleTargets = new ArrayList<>(); // 만들 수 있는 당첨번호들

        ArrayList<CardPair> pairs = new ArrayList<CardPair>(); // 페어리스트

        for(int p: cards){
            for(int q:cards){
                pairs.add(new CardPair(p, q));
            }
        }
        // pairs : n^2가지 두 장의 카드 조합 페어들이 저장되어 있다
        Collections.sort(pairs); // 이진검색을 위한 정렬

        for(int k : target){
            boolean possible = false;
            // k = (p + q) + (r + s) 가 되는 숫자가 있는지 검사
            for(CardPair pair : pairs){ // 페어를 하나 골라
                int r_plus_s = k - pair.sumOfCards;
                CardPair targetPair = new CardPair(r_plus_s);
                if(Collections.binarySearch(pairs, targetPair) >= 0){ // targetPair가 pairs 와 같은 값이 있다면
                    possible = true;
                    break;
                }
            }
            if(possible){ // 하나 이상의 정답이 발견됐다면 = k는 네 숫자의 합으로 만들 수 있다
                possibleTargets.add(k);
            }
        }
        return possibleTargets;
    }

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

        int[] cards = new int[n];
        int[] targets = new int[m];

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

        ArrayList<Integer> answers = getPossibleTargets(n, m, cards, targets);

        if(answers.size() == 0)
        { // 가능한 당첨번호가 없다면 NO를 출력한다
            System.out.print("NO");
        }else
        { //가능한 당첨번호가 존재한다면 그 목록을 출력한다.
            for(int i = 0 ; i < answers.size() ; i++)
            {
                if( i > 0 )
                {
                    System.out.print(" ");
                }
                System.out.print(answers.get(i));
            }
        }

    }
}
// Comparable 인터페이스 : 객체간의 정렬, 비교, 탐색
class CardPair implements Comparable<CardPair> {
    int card1;
    int card2;
    int sumOfCards; // 두 카드의 합

    // 두개의 카드 정보를 알 때
    CardPair(int card1, int card2){
        this.card1 = card1;
        this.card2 = card2;
        this.sumOfCards = this.card1 + this.card2;
    }

    // 두 카드의 정보는 모르고 합은 알 때
    CardPair(int sumOfCards){
        this.sumOfCards = sumOfCards;
        this.card2 = -1;
        this.card1 = -1;
    }

    // 두 숫자의 합을 기준으로 정렬, 탐색
    @Override
    public int compareTo(CardPair o) {
        return this.sumOfCards - o.sumOfCards;
    }
}