https://www.acmicpc.net/problem/2981
풀이
처음에는 문제 그대로 N개의 숫자를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려 했다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
int min, i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
min = arr[0];
for (i = 2; i < arr[1]; i++) {
int div = arr[0] % i;
boolean flag = true;
for (int idx = 1; idx < n; idx++) {
if (arr[idx] % i != div) {
flag = false;
break;
}
}
if (flag) list.add(i);
}
for (int num : list)
sb.append(num + " ");
System.out.println(sb);
}
}Arrays.sort(arr);:arr정렬
arr[0]이 arr의 가장 작은 값이 된다.
i가arr[0]보다 커지면 나머지는arr[0]이 되기 때문에i를arr[1]전까지만 for문을 돌린다.
=>for (i = 2; i < arr[1]; i++)
하지만 숫자가 10억까지 입력할 수 있기 때문에 시간 초과가 났다. 그래서 두 수의 차이를 이용하여 실행시간을 줄인다.
a = b * i + d
e = u * i + d
e - a = (u-b) * i두 수의 차이를 gap 배열에 저장하고 그 차이가 i로 나누어 떨어지면 된다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] gap = new int[n-1];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
int i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
for (i = 1; i < n; i++) {
// gap에 두 수의 차이를 저장
gap[i-1] = arr[i] - arr[i-1];
}
for (i = 2; i < arr[1]; i++) {
boolean flag = true;
for (int idx = 0; idx < n-1; idx++) {
if (gap[idx] % i != 0) {
flag = false;
break;
}
}
if (flag) list.add(i);
}
for (int num : list)
sb.append(num + " ");
System.out.println(sb);
}
}하지만 76%에서 시간 초과가 뜬다.
생각해보니 gap[idx] % i != 0이면 i는 답이 될 수 없다.
=> 즉 gap[idx] 보다 i가 크면 그 이후의 숫자부터는 답이 될 수 없으므로 gap에서 가장 작은 값까지만 for문을 도리면 된다. 그래서 gap을 정렬한 다음 for (i = 2; i <= gap[0]; i++) 로 for문 을 돌렸다. 그 결과 통과할 수 있었다.
코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
int[] gap = new int[n-1];
StringBuilder sb = new StringBuilder();
ArrayList<Integer> list = new ArrayList<>();
int i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
// gap에 두 수의 차이를 저장
for (i = 1; i < n; i++) {
gap[i-1] = arr[i] - arr[i-1];
}
Arrays.sort(gap);
int min = gap[0];
for (i = 2; i <= min; i++) {
boolean flag = true;
for (int idx = 0; idx < n-1; idx++) {
if (gap[idx] % i != 0) {
flag = false;
break;
}
}
if (flag) list.add(i);
}
for (int num : list)
sb.append(num + " ");
System.out.println(sb);
}
}다른 풀이 - 2
두 수의 차이를 gap 배열에 저장하고 그 차이가 i로 나누어 떨어지면 된다.
=> 두 수의 차이의 최대공약수를 구한 다음 계속해서 최대공약수를 업데이트하여 최종적으로 모든 수(두 수의 차이)의 최대공약수를 구한다. 그리고 그 수의 2 이상의 약수를 출력한다.
gap 배열을 사용할 필요 없으며 최대공약수를 구하는 gcd 함수를 사용한다.
import java.io.*;
import java.util.*;
public class Main {
public static int gcd(int a, int b) {
int r;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringBuilder sb = new StringBuilder();
int i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int val = arr[1] - arr[0];
for (i = 2; i < n; i++) {
val = gcd(val, arr[i] - arr[i-1]);
}
for (i = 2; i <= val; i++) {
if (val % i == 0)
sb.append(i + " ");
}
System.out.println(sb);
}
}다른 풀이 - 3
최대공약수의 약수를 굳이 끝까지 탐색할 필요가 없다. 굳이 약수를 찾는데 val까지 찾을 필요 없이 val의 절반까지만 탐색해도 된다.
물론 이 때 주의해야 할 것은 마지막에 최대공약수 자신도 출력해주어야 한다.
import java.io.*;
import java.util.*;
public class Main {
public static int gcd(int a, int b) {
int r;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringBuilder sb = new StringBuilder();
int i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int val = arr[1] - arr[0];
for (i = 2; i < n; i++) {
val = gcd(val, arr[i] - arr[i-1]);
}
for (i = 2; i <= val/2; i++) {
if (val % i == 0)
sb.append(i + " ");
}
sb.append(val);
System.out.println(sb);
}
}다른 풀이 - 4
탐색 범위를 (val / 2) 가 아닌 제곱근, 즉 √val 까지만 탐색하여 i와 val/i를 ArrayList에 넣고 리스트를 정렬한 다음 출력한다. 물론 이 때 주의해야 할 것은 마지막에 최대공약수 자신도 list에 넣어주어야 한다.
import java.io.*;
import java.util.*;
public class Main {
public static int gcd(int a, int b) {
int r;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] arr = new int[n];
StringBuilder sb = new StringBuilder();
int i;
for (i = 0; i < n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(arr);
int val = arr[1] - arr[0];
for (i = 2; i < n; i++) {
val = gcd(val, arr[i] - arr[i-1]);
}
ArrayList<Integer> list = new ArrayList<>();
for (i = 2; i <= Math.sqrt(val); i++) {
if (Math.sqrt(val) == i) {
list.add(i);
}
else if (val % i == 0) {
list.add(i);
list.add(val/i);
}
}
list.add(val);
Collections.sort(list);
for (int num : list)
sb.append(num + " ");
System.out.println(sb);
}
}
4번째 방법이 메모리와 실행시간이 가장 작다.
최대공약수의 약수를 탐색하는 탐색 범위를 줄일 때 가장 실행시간이 크게 감소한 것을 볼 수 있다.
