길이 $N$의 양의 정수로 이루어진 수열 $A$가 주어질 때, 중복 집합(multiset) $M$을 다음과 같이 정의하자. 중복 집합이란, 중복된 원소를 허용하는 집합을 의미한다.
$$ M=\{A_{i}\times A_{j} \mid 1\leq i,j\leq N\} $$
중복 집합 $M$의 모든 원소가 주어질 때, 원래의 수열 $A$를 찾아보자.
첫 번째 줄에 수열 $A$의 길이인 양의 정수 $N$이 주어진다. $(1\leq N \leq 1\,000)$
두 번째 줄에 중복 집합 $M$의 원소인 $m_1,m_2,\dots, m_{N^2}$이 공백으로 구분되어 주어진다. $\left(1\leq m_i \leq 10^{18}\right)$
만약 원래의 수열 $A$를 구성할 수 있다면, 첫 번째 줄에 YES를 출력하고 두 번째 줄에 수열 $A$의 원소인 $A_{1}, A_{2}, \dots , A_{N}$을 공백으로 구분하여 출력한다.
그렇지 않다면 첫 번째 줄에 NO를 출력한다.
가능한 답이 여러 개라면 그중 아무거나 출력한다.
3
1 2 2 1 2 1 1 2 4
YES
1 1 2
2
1 3 4 9
NO
알고리즘의 설계 난이도도 높았고, 동시에 map에 익숙하지 않으면 상당히 꼬여 버리는 문제.
일단, 한 가지 생각해 보자. 중복 집합 $M$에는 반드시 한 개 이상의 최댓값이 존재할 것이다. 이 최댓값은 당연하겠지만, $A$의 최댓값끼리 곱해야 나오는 값일 것이며, 따라서 다음이 반드시 성립해야 한다.
이렇게 $A$의 최댓값 $A_N$을 찾았다면, (정상적으로 찾았다는 가정 하에) $M$의 원소 하나는 등장했으니 셈에서 제외하면 된다.