5회차 - 알고리즘 기록 : 네 카드

📌 네 카드

예인이가 살고 있는 이상한 나라에서는 독특한 복권제도가 존재한다.

이상한 나라에서는 매 주 당첨 될 자연수 번호를 정해두며, 복권을 구매한 사람은 그 자리에서 수 많은 카드들 중 하나를 뽑을 수 있는 기회가 네 번 주어진다.

즉, 똑같은 카드를 네 번 뽑을 수 도 있다.

이렇게 네 번에 걸쳐 뽑은 카드들에 적혀있는 네 자연수를 더하여 당첨 번호로 지정된 자연수와 일치한다면 그 사람은 당첨되는 것이다.

 복권 담당자인 미주는 이번 주에 복권에 사용 될 당첨 번호들을 정하려고 한다.

하지만 매 번 실제로 그 당첨번호가 네 카드에 적힌 숫자들의 합으로 만들어 질 수 있는지 (즉, 실제로 당첨될 수 있는 번호인지) 검사하는 과정이 너무 번거로워 고민을 하고 있다.

미주를 도와서 주어진 카드를 조합해 당첨 번호들을 만들 수 있는지 판단하는 프로그램을 작성해주자.

 

입력 형식

 첫 줄에는 사용할 카드의 수 N과 당첨 번호의 숫자 M이 공백으로 구분되어 주어진다.

N은 1이상 1,000이하의 자연수이며 M은 1이상 100이하의 자연수이다.

두 번째 줄에는 N개의 카드에 적힌 숫자들이 공백으로 구분되어 1이상 1억 이하의 자연수로 주어진다. 

세 번째 줄에는 M개의 이번 주에 사용 될 당첨번호들이 공백으로 구분되어 주어진다. 당첨번호들은 모두 서로다른 1이상 4억 이하의 자연수이다. 

 

출력 형식

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

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

 

예시

- 입력

10 5
2 4 6 8 10 12 14 16 18 20
6 7 8 9 10

 

- 출력

 

8 10

 

코드 풀이

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


public class Main {
	public static final Scanner scanner = new Scanner(System.in);

	/**
	 * 중복을 포함해 네 카드의 합으로 만들 수 있는 당첨번호들의 리스트를 반환하는 함수
	 * @param n     카드의 수
	 * @param m     검사하려는 당첨번호의 수
	 * @param cards   각 카드에 적힌 숫자들
	 * @param target  검사하려는 각 당첨번호 리스트
	 * @return      네 카드의 합으로 표현될 수 있는 당첨번호들의 오름차순 리스트
	 */
	public static ArrayList<Integer> getPossibleTargets(int n, int m, int[] cards, int[] target)
	{
		ArrayList<Integer> possibleTargets = new ArrayList<>(); //만들 수 있는 당첨번호들

		// 두 카드의 합을 모두 저장한다.
		ArrayList<CardPair> pairs = new ArrayList<>();
		for(int i = 0; i < n ; i ++)
		{
			for(int j = 0 ; j <= i; j++)
			{   // 모든 카드의 조합 <i, j>에 대하여, 두 카드를 짝지은 정보를 모두 저장한다
				CardPair pair = new CardPair( cards[i], cards[j] );
				pairs.add(pair);
			}
		}

		// 바이너리 서치를 할 수 있도록 정렬한다.
		// 클래스 내에서 비교 연산자를 정의했기 때문에, 정렬할 수 있다.
		Collections.sort(pairs);

		for(int k : target)
		{ // 검사해 볼 모든 당첨 후보번호 k에 대하여
			boolean possible = false;
			for(CardPair knownPair : pairs)
			{   // 임의의 두 카드 < p, q >를 나타내는 짝 knownPair에 대하여
				int x = knownPair.sumOfCards; // x = ( p + q ) 라고 하자.

				// 남은 두 카드를 r, s라고 한다면
				// y = r + s라고 할 때 아래가 성립한다.
				int y = k - x;
				CardPair targetPair = new CardPair(y); //두 카드의 합이 y가 되는 짝이 있다고 가정하자

				//그런 짝이 pairs에 존재한다는 말은?
				//기존에 존재하던 cards[]의 두 카드의 합으로, y를 만들어낼 수 있다!
				int pairIndex = Collections.binarySearch(pairs, targetPair);
 				if( pairIndex >= 0)
				{   // 그러므로, k는 네 카드의 합으로 표현 가능하다
					possible = true;

					// 아래와 같이 어떤 네 카드가 선택되었는지도 알 수 있다!
					//CardPair pair1 = knownPair;
					//CardPair pair2 = pairs.get( pairIndex );
					break;
				}
			}

			if(possible)
			{
				possibleTargets.add(k);
			}
		}

		Collections.sort(possibleTargets);
		return possibleTargets;
	}

	public static void main(String[] args) throws Exception {
		int n = scanner.nextInt();  // 카드의 수
		int m = scanner.nextInt();  // 검사 할 후보 당첨번호의 수

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

		// 각 카드 정보를 입력받는다
		for(int i = 0 ; i < n ; i ++)
		{
			cards[i] = scanner.nextInt();
		}

		// 각 당첨번호를 입력받는다
		for(int i = 0 ; i < m ; i ++)
		{
			targets[i] = scanner.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));
			}
		}
	}
}


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.card1 = -1;
		this.card2 = -1;
	}

	// 두 카드의 합으로 짝들의 대소 관계를 정의한다.
	@Override
	public int compareTo(CardPair o) {
		return this.sumOfCards - o.sumOfCards;
	}
}