6회차 - 알고리즘 기록 : 네 카드 (어려웠던거 다시!)

---

 

 중복을 포함해 네 카드의 합으로 만들 수 있는 당첨번호들의 리스트를 반환하는 함수

     @param n         카드의 수
     @param m        검사하려는 당첨번호의 수
     @param cards  각 카드에 적힌 숫자들
     @param target  검사하려는 각 당첨번호 리스트
     @return             네 카드의 합으로 표현될 수 있는 당첨번호들의 오름차순 리스트

 

---

네 카드는 모든 카드의 네 가지 수의 조합이 타겟과 같은가 ? 라는 질문을 하는 알고리즘이다.

 

네 카드는 즉 ( 하나의 카드 + 하나의 카드 ) + ( 하나의 카드 + 하나의 카드 ) 이다.

 

CardPair 는 모든 두 개의 카드로 생성되는 객체다. 즉 두 개의 카드의 합이다.

모든 cards 의 배열을 순회하면서 모든 두 개의 카드의 조합을 생성한다.

 

ArrayList<CardPair> pairs = new ArrayList<>();

for( p : cards ){

    for( q : cards ){

        pairs.add( new CardPair(q,p) );

    }

}

 

이제 pairs 에는 모든 두 개의 카드의 조합이 담긴셈이다.

 

우리는 Comparable 를 이용해야하기 때문에 모든 원소가 정렬이 되어있어야 한다.

Collections.sort(pairs);

 

possibleTargets 에 가능한 조합을 담을 것이다.

ArrayList<Integer> possibleTargets = new ArrayList()<>;

 

target 을 기준으로 for 문을 순회한다.

possible 에는 네 숫자의 조합이 있는지 검사할 예정이다.

 

for( int k : target ){

    boolean possible = false;

    

    for(CardPair pair : paris){

        int r_plus_s = k - pair.sumofCards;

 

        CardPair targetPair = new CardPair( r_plus_s );

    

        if(Collections.binarySearch( pairs, targetPair ) >= 0){

            possible = true;

            break;

        }

    }

 

    if(possible){

        possibleTargets.add(k);

    }

}

 

 

Collections.sort(possibleTargets);