0
6
1
1 4 7 10 11 12

0
4 10

0
import java.io.BufferedReader;
1
import java.io.BufferedWriter;
2
import java.io.IOException;
3
import java.io.InputStreamReader;
4
import java.io.OutputStreamWriter;
5
import java.util.Arrays;
6
import java.util.LinkedList;
7

8
/**
9
 * 백준 전체 1017 문제 알고리즘 클래스
10
 *
11
 * @author RWB
12
 * @see <a href="https://blog.itcode.dev/posts/2021/06/26/a1017">1017 풀이</a>
13
 * @since 2021.06.26 Sat 03:19:32
14
 */
15
public class Main
16
{
17
    // 에라토스 테네스의 체 배열 (소수 판별용)
18
    private static final boolean[] IS_NOT_PRIME = eratosthenes();
19
    
20
    // 왼쪽 배열 (이분매칭의 기준)
21
    private static int[] left;
22
    
23
    // 오른쪽 배열
24
    private static int[] right;
25
    
26
    // 노드 연결 여부
27
    private static boolean[][] hasNode;
28
    
29
    // 방문 여부
30
    private static boolean[] isVisit;
31
    
32
    // 매칭된 수
33
    private static int[] matched;
34
    
35
    // 현재 선택 중인 수
36
    private static int selected;
37
    
38
    /**
39
     * 메인 함수
40
     *
41
     * @param args: [String[]] 매개변수
42
     *
43
     * @throws IOException 데이터 입출력 예외
44
     */
45
    public static void main(String[] args) throws IOException
46
    {
47
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
48
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
49
        
50
        // 입력값 갯수
51
        int N = Integer.parseInt(reader.readLine());
52
        
53
        // 입력값 배열
54
        int[] numbers = Arrays.stream(reader.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
55
        
56
        // 첫 번째 수가 홀수일 경우
57
        if (numbers[0] % 2 != 0)
58
        {
59
            // 왼쪽 배열에 홀수를 할당
60
            left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
61
            right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
62
        }
63
        
64
        // 첫 번째 수가 짝수일 경우
65
        else
66
        {
67
            // 왼쪽 배열에 짝수를 할당
68
            left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
69
            right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
70
        }
71
        
72
        // 홀수 배열과 짝수 배열의 수가 동일할 경우 (이분매칭 가능)
73
        if (left.length == right.length)
74
        {
75
            hasNode = new boolean[left.length][right.length];
76
            
77
            // left의 첫 번째 행은 기준 매칭이므로 이분 매칭에서 제외한다.
78
            for (int i = 1; i < left.length; i++)
79
            {
80
                for (int j = 0; j < right.length; j++)
81
                {
82
                    int ref = left[i] + right[j];
83
                    
84
                    // left[i] + right[j]의 값이 소수일 경우
85
                    if (!IS_NOT_PRIME[ref])
86
                    {
87
                        // 노드를 연결한다.
88
                        hasNode[i][j] = true;
89
                    }
90
                }
91
            }
92
            
93
            LinkedList<Integer> list = new LinkedList<>();
94
            
95
            // 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
96
            for (int i = 0; i < N / 2; i++)
97
            {
98
                // left[0]와 right[i]의 합이 소수일 경우
99
                if (!IS_NOT_PRIME[left[0] + right[i]])
100
                {
101
                    selected = i;
102
                    
103
                    int size = bipartite();
104
                    
105
                    // 모든 요소가 매칭될 경우
106
                    if (size == N / 2)
107
                    {
108
                        list.add(right[selected]);
109
                    }
110
                }
111
            }
112
            
113
            // 하나도 매칭되지 않은 경우
114
            if (list.size() == 0)
115
            {
116
                writer.write("-1");
117
            }
118
            
119
            // 매칭이 하나 이상 있을 경우
120
            else
121
            {
122
                // 오름차순으로 정렬
123
                list.sort(Integer::compareTo);
124
                
125
                StringBuilder builder = new StringBuilder();
126
                
127
                for (int item : list)
128
                {
129
                    builder.append(item).append(" ");
130
                }
131
                
132
                writer.write(builder.toString().trim());
133
            }
134
        }
135
        
136
        // 홀수 배열과 짝수 배열의 수가 동일하지 않을 경우 (이분매칭 불가능)
137
        else
138
        {
139
            writer.write("-1");
140
        }
141
        
142
        writer.newLine();
143
        writer.close();
144
        reader.close();
145
    }
146
    
147
    /**
148
     * 이분 매칭 갯수 반환 함수
149
     *
150
     * @return [int] 이분 매칭 갯수
151
     */
152
    private static int bipartite()
153
    {
154
        // 이미 left[0]과 right 요소 하나가 선택됨
155
        int size = 1;
156
        
157
        matched = new int[left.length];
158
        
159
        Arrays.fill(matched, -1);
160
        
161
        for (int i = 1; i < left.length; i++)
162
        {
163
            isVisit = new boolean[left.length];
164
            
165
            // 매칭 가능할 경우
166
            if (dfs(i))
167
            {
168
                size++;
169
            }
170
        }
171
        
172
        return size;
173
    }
174
    
175
    /**
176
     * DFS 알고리즘 결과 반환 함수
177
     *
178
     * @param num: [int] 시작점
179
     *
180
     * @return [int] 매칭 갯수
181
     */
182
    private static boolean dfs(int num)
183
    {
184
        // 첫 방문일 경우
185
        if (!isVisit[num])
186
        {
187
            isVisit[num] = true;
188
            
189
            for (int i = 0; i < right.length; i++)
190
            {
191
                // 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
192
                if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
193
                {
194
                    // 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
195
                    if (matched[i] == -1 || dfs(matched[i]))
196
                    {
197
                        matched[i] = num;
198
                        
199
                        return true;
200
                    }
201
                }
202
            }
203
        }
204
        
205
        return false;
206
    }
207
    
208
    /**
209
     * 아레토스 테네스의 체 배열 반환 함수
210
     *
211
     * @return [boolean[]] 아레토스 테네스의 체
212
     */
213
    private static boolean[] eratosthenes()
214
    {
215
        boolean[] isNotPrime = new boolean[2000];
216
        
217
        isNotPrime[0] = true;
218
        isNotPrime[1] = true;
219
        
220
        int maxPrime = (int) Math.ceil(Math.sqrt(2000));
221
        
222
        for (int i = 2; i < maxPrime; i++)
223
        {
224
            // 소수일 경우
225
            if (!isNotPrime[i])
226
            {
227
                for (int j = i + i; j < isNotPrime.length; j += i)
228
                {
229
                    // 아직 소수가 아님을 표시하지 않았을 경우
230
                    if (!isNotPrime[j])
231
                    {
232
                        // 소수의 배수는 소수가 아니므로 제외함
233
                        isNotPrime[j] = true;
234
                    }
235
                }
236
            }
237
        }
238
        
239
        return isNotPrime;
240
    }
241
}

0
// 첫 번째 수가 홀수일 경우
1
if (numbers[0] % 2 != 0)
2
{
3
    // 왼쪽 배열에 홀수를 할당
4
    left = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
5
    right = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
6
}
7

8
// 첫 번째 수가 짝수일 경우
9
else
10
{
11
    // 왼쪽 배열에 짝수를 할당
12
    left = Arrays.stream(numbers).filter(value -> value % 2 == 0).toArray();
13
    right = Arrays.stream(numbers).filter(value -> value % 2 != 0).toArray();
14
}

0
// 대상 숫자
1
int number = 1000;
2

3
// 소수 여부
4
boolean isPrime = true;
5

6
// 가장 작은 소수인 2부터 대상의 제곱근까지 나누기
7
for (int i = 2; i <= Math.sqrt(number); i++)
8
{
9
    // 나누어 떨어지는 수가 있을 경우
10
    if (number % i == 0)
11
    {
12
        isPrime = false;
13
        break;
14
    }
15
}

0
// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
1
for (int i = 0; i < N / 2; i++)
2
{
3
    // left[0]와 right[i]의 합이 소수일 경우
4
    if (!IS_NOT_PRIME[left[0] + right[i]])
5
    {
6
        selected = i;
7
        
8
        int size = bipartite();
9
        
10
        // 모든 요소가 매칭될 경우
11
        if (size == N / 2)
12
        {
13
            list.add(right[selected]);
14
        }
15
    }
16
}

0
/**
1
 * 이분 매칭 갯수 반환 함수
2
 *
3
 * @return [int] 이분 매칭 갯수
4
 */
5
private static int bipartite()
6
{
7
    // 이미 left[0]과 right 요소 하나가 선택됨
8
    int size = 1;
9
    
10
    matched = new int[left.length];
11
    
12
    Arrays.fill(matched, -1);
13
    
14
    for (int i = 1; i < left.length; i++)
15
    {
16
        isVisit = new boolean[left.length];
17
        
18
        // 매칭 가능할 경우
19
        if (dfs(i))
20
        {
21
            size++;
22
        }
23
    }
24
    
25
    return size;
26
}
27

28
/**
29
 * DFS 알고리즘 결과 반환 함수
30
 *
31
 * @param num: [int] 시작점
32
 *
33
 * @return [int] 매칭 갯수
34
 */
35
private static boolean dfs(int num)
36
{
37
    // 첫 방문일 경우
38
    if (!isVisit[num])
39
    {
40
        isVisit[num] = true;
41
        
42
        for (int i = 0; i < right.length; i++)
43
        {
44
            // 연결된 노드가 있으며, 첫 번째 숫자와 매칭된 숫자가 아니며, 소수일 경우
45
            if (hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]])
46
            {
47
                // 매칭이 아직 되지 않았거나, 매칭된 숫자가 다른 숫자와 매칭될 수 있을 경우
48
                if (matched[i] == -1 || dfs(matched[i]))
49
                {
50
                    matched[i] = num;
51
                    
52
                    return true;
53
                }
54
            }
55
        }
56
    }
57
    
58
    return false;
59
}