𝝅번째 알파카의 개발 낙서장

screen

[백준 / JAVA] 백준 알고리즘 1017번 소수 쌍

posts

알고리즘

시리즈 톺아보기

백준 알고리즘

백준 알고리즘
count

소수 쌍 🔗

랭크 사용 언어
image JAVA

🔗 전체 1017번 문제

조건 🔗

시간제한 메모리 제한
2초 128MB

문제 🔗

지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, 가 있다고 하자. 지민이는 다음과 같이 그룹지을 수 있다.

, ,
또는
, ,

수의 리스트가 주어졌을 때, 지민이가 모든 수를 다 짝지었을 때, 첫 번째 수와 어떤 수를 짝지었는지 오름차순으로 출력하는 프로그램을 작성하시오. 위의 예제에서 으로 소수이다. 그러나, 남은 4개의 수를 합이 소수가 되게 짝지을 수 있는 방법이 없다. 따라서 예제의 답은 4, 10이다.

입력 🔗

첫째 줄에 리스트의 크기 이 주어진다. N은 50보다 작거나 같은 자연수이며, 짝수이다. 둘째 줄에 리스트에 들어있는 수가 주어진다. 리스트에 들어있는 수는 1,000보다 작거나 같은 자연수이며, 중복되지 않는다.

출력 🔗

첫째 줄에 정답을 출력한다. 없으면 -1을 출력한다.

케이스 🔗

예제 1 🔗

  • 입력

TC

06
11 4 7 10 11 12
  • 출력

TC

04 10

풀이 🔗

1014번 컨닝문제를 통해 이분 매칭을 접한 덕분인지, 지금까지 푼 플래티넘 중에서는 그나마 좀 이해되는 문제였다.

역시 내용이 다소 난해한데, 알고리즘이 요구하는 동작은 다음과 같이 정리할 수 있다. 입력된 6개의 숫자 배열 이 있다고 가정하자. 배열의 숫자를 한 쌍씩 짝지어 더하면 총 3개의 수가 나온다. 이렇게 짝지어 더한 수가 모두 소수일 경우, 입력의 첫 번째 숫자와 매칭된 숫자들을 오름차순으로 정렬하여 출력하는 문제다.

예제에서도 설명해주듯이, 짝지은 수가 모두 소수인 경우는 , , , , 가 된다. 입력의 가장 첫 번째 숫자가 1이므로, 1와 매칭된 4, 10이 정답이 된다.

소수 판별하기🍳 🔗

이제 좀 더 세부적인 내용을 살펴보자. 문제 해결의 핵심은 소수다. 이 알고리즘에선 소수 판별이 필요하다. 많은 판별방법이 있지만, 가장 대표적인 에라토스 테네스의 체를 활용하면 어렵지 않게 해결할 수 있다.

요소 한 쌍씩 그룹화하기 🔗

소수 판별 방법도 마련했겠다, 입력된 숫자 배열을 적절히 짝지어야한다. 핵심은 짝지은 수의 합이 소수가 되는 것. 요소를 한번씩 다 더해보는 방법도 있겠지만, 배열의 크기가 커질 수록 요구되는 연산량 또한 높아지므로 적절하지 않다. 즉, 가능성 있는 조합으로만 그룹화해야한다.

소수에 대해 생각해보자. 소수는 1과 자기 자신으로만 나눠지는 수다. 즉, 반드시 소수는 홀수여야 한다. 이 전제를 확장하면 짝지은 수의 합이 홀수여야한다. 두 수를 더했을 때 홀수가 나오는 경우는 홀수 + 짝수로 한 가지 경우의 수만 존재한다.

따라서 우리는 입력값을 홀수와 짝수 그룹으로 나누어 각 그룹끼리만 더하면 결과는 모두 홀수일 것이므로, 해당 수는 소수일 가능성이 있다. 두 개의 그룹을 겹치지 않게 조합해야하므로 이분 매칭이 적절한 해답이 될 수 있다. 각 그룹은 홀수와 짝수로 나누고, 더했을 때 소수가 되는 쌍을 노드로 연결하면 이분 매칭으로 접근 가능하다.

image

위 그림은 예제 1을 홀수와 짝수 그룹으로 나눠 이분매칭으로 표시한 그림이다. 위 숫자를 6개의 숫자를 매칭하면 3개의 노드가 나올 것이다. 각 숫자를 더하기 위해선 반드시 하나의 쌍을 이뤄야하므로, 이분 매칭의 결과는 반드시 가 되어야 한다.

예제의 가장 첫 번째 수는 1이다. 즉, 우리는 모든 요소쌍의 합이 모두 소수가 되는 조합을 찾고 해당 조합들에서 각각 1과 매칭되는 숫자를 구해야한다. 이를 확장시키면, 1과 짝을 이루는 수를 더한 값이 소수가 아닐 경우 애초에 비교할 필요가 없다.

위 그림의 매칭 결과가 3이 나온다면, 모든 요소를 적절히 짝지어 더한 값이 모두 소수가 되는 조합이 있다는 뜻이다. 해당 조합을 저장하여 1과 짝지은 값을 찾으면 될 것이다.
만약, 홀수와 짝수의 갯수가 일치하지 않을 경우, 매칭이 불가능하므로 문제에 제시한 조건에 따라 -1을 반환해야 한다.

image

1과 더했을 때 소수가 되는 요소는 4, 10, 12 모두 해당하므로 이를 모두 노드로 연결할 수 있다. 1과 매칭 가능한 요소 중 하나를 연결하면, 나머지 4개 요소에 대해서만 이분 매칭을 진행할 수 있다.

image

만약, 1과 4를 매칭했다면 나머지 4개 요소에 대한 소수 매칭은 그림과 같이 표현할 수 있다. , 조합의 합이 모두 소수이므로, , , 조합은 알고리즘의 조건에 부합한다. 따라서 4는 정답에 포함된다.

image

만약, 1과 12가 매칭된다면 어떨까? 이는 위 그림과 같이 표시할 수 있다. 7의 경우 4와 10 중 어떤걸 조합해도 소수지만, 11의 경우 4와 10 모두 소수가 아니므로 어떤식으로 매칭해도 4개 요소의 매칭 결과는 1이 된다. 즉, 1과 매칭된 조합 하나를 더한 최종 매칭 수는 2이므로 의 값에 부합하지 않으므로 해당 조합은 정답이 될 수 없다.
따라서 예제의 결과는 출력과 같이 4 10이 된다.

전체 소스 🔗

JAVA

0import java.io.BufferedReader;
1import java.io.BufferedWriter;
2import java.io.IOException;
3import java.io.InputStreamReader;
4import java.io.OutputStreamWriter;
5import java.util.Arrays;
6import 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 */
15public 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}

편의상 항상 왼쪽을 기준으로 매칭한다. 올바른 조합 중 첫 번째 수와 매칭되는 수를 찾는 것이 목표인데, 첫 번째 수는 홀수, 짝수 모두 올 수 있다. 따라서 홀수가 먼저오냐, 짝수가 먼저오냐에 따라 해당하는 분류를 기준 배열로 할당한다.

JAVA

0// 첫 번째 수가 홀수일 경우
1if (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// 첫 번째 수가 짝수일 경우
9else
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}

해당 소스는 위와 같다. 왼쪽 배열 left를 기준으로하여 홀수가 올 경우 left에 홀수 배열을, 아닐 경우 짝수 배열을 할당한다.

소수 판별은 에라토스 테네스의 체 알고리즘을 통해, 요소로 올 수 있는 최대값인 2,000개 배열에 대한 소수 배열을 준비한다.

잠깐, 문제에서는 요소로 올 수 있는 최대값이 1,000이라는데요?
홀수와 짝수를 더하므로, 요소의 최대값은 각 요소의 최대값을 더한 999 + 1,000 = 1,999가 됩니다.

배열이 2000개까지밖에 안 되므로, 연산할 때마다 비교하는 것 보다 미리 배열을 선언해서 비교하는 게 훨씬 효율적이라 판단했다.
만약 연산할 때마다 비교하려면, 비교할 수의 제곱근을 구하고, 2부터 제곱근까지 나눈다. 중간에 정확히 나누어 떨어지는 수가 있을 경우, 그 수는 소수가 아니다.

JAVA

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

대충 위 형식처럼 짜면 된다.

JAVA

0// 첫 번째 수와 상대 그룹의 요소를 하나씩 매칭해본다.
1for (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}

그룹을 나누었으면, 입력값의 첫 번째 수 와 하나씩 매칭하여 기준 매칭을 선정한다. !IS_NOT_PRIME[left[0] + right[i]]을 통해 매칭이 소수일 경우에만 진행한다. 소수가 아닐 경우 비교해볼 필요도 없으니. selected는 현재 와 매칭된 요소를 의미한다. 이게 왜 필요하냐면, 와 매칭된 요소의 경우 다른 요소와 매칭될 수 없으므로 매칭에서 제외해야 한다.

이는 위 그림과 같이 나타낼 수 있다. 이미 1이 10과 매칭되었으므로, 10과 연결된 7, 11의 노드를 제거해야 정상적으로 매칭할 수 있다. 연결된 노드는 hasNode 배열에서 관리하고 있다. 예제 1을 기준으로 hasNode의 값은 다음과 같다.

4 10 12
1 true true true
7 true true true
11 false false true

만약 여기서, 1과 10을 매칭할 경우 hasNode는 아래와 같다.

4 10 12
1 false true false
7 true false true
11 false false true

1과 10에 연결된 다른 노드를 모두 제거하고, hasNode[1][10] = true로 지정해야 한다. 임시 배열을 선언해서 변경하는 경우도 있겠지만, 배열 연산 오버헤드를 줄이기 위해 selected = 10으로 지정하여 DFS 알고리즘 수행 시 selected와 동일한 인덱스를 false로 인식하게끔 설계했다.

JAVA

0/**
1 * 이분 매칭 갯수 반환 함수
2 *
3 * @return [int] 이분 매칭 갯수
4 */
5private 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 */
35private 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}

이분 매칭 소스는 위와 같다. bipartite()는 기본적인 이분 매칭 알고리즘과 크게 다르지 않다. size가 1부터 시작하는 이유는, 이미 입력의 첫 번째 수 left[0]과 합이 소수를 만족하는 right[m]과 매칭되었기 때문이다.

dfs()에서 조건에 따라 필터링이 진행된다. 조건식은 hasNode[num][i] && i != selected && !IS_NOT_PRIME[left[num] + right[i]]와 같다.

  • hasNode[num][i]: left[num]right[i]가 서로 연결되어 있는지 (소수)
  • i != selected: left[num]right[i]와 매칭되지 않았는지
  • !IS_NOT_PRIME[left[num] + right[i]]: left[num]right[i] 소수인지

위 조건식을 모두 만족할 경우에만 매칭을 수행한다.

이 반드시 짝수거나, 입력된 숫자의 홀수, 짝수가 반드시 동일하다는 조건이 존재하지 않으므로, 이 경우 -1을 출력해야한다. 또한, 모든 조건이 일치해도 매칭이 하나도 되지 않을 경우 역시 -1을 출력해야한다.

분류 🔗

  • 수학
  • 정수론
  • 소수 판정
  • 이분 매칭
  • 에라토스 테네스의 체