[BackJoon]2981번

문제

 

트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 

경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다.

상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다.

먼저 근처에 보이는 숫자 N개를 종이에 적는다. 

그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. 

M은 1보다 커야 한다.

N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100)

다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 

이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. 

같은 수가 두 번 이상 주어지지 않는다.

항상 M이 하나 이상 존재하는 경우만 입력으로 주어진다.

 

출력

 

첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력한다. 

이때, M은 증가하는 순서이어야 한다.

 

풀이

 

며칠동안 매달렸지만 메모리 초과를 이겨내지 못했던 문제이다.

 

무식하게 스트림을 써가며 전부 계산하려고 했기 때문인데, 포기하고 살다보니 좋은 생각이 나서 풀 수 있었다.

 

예를 들어 주어진 예제 중 하나를 보면 숫자가 총 다섯 개가 들어온다.

5 17 23 14 83

그런데 이 수를 특정한 수로 나누었을 때 나머지가 같으려면,

 

위의 각 숫자를 빼주었을 때의 값이 아래와 같이 그 특정한 수의 배수가 되어야 한다.

12 6 9 69

임의로 작은 수에서 큰 수를 뺐을 땐 절대값을 취해주었다.

 

이어서 위 숫자들의 최대공약수를 구한 뒤에 그 약수들을 찾으면 문제는 끝난다.

 

리스트와 스트림을 사용해 코드가 조금 길어진 느낌이 있지만, 어쨌거나 나의 답은 아래와 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.IntStream;

public class Prob2981_5 {
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(br.readLine());

		List<Integer> list = new ArrayList<>();
		List<Integer> subList = new ArrayList<>();

		for (int i = 0; i < n; i++) {
			list.add(Integer.parseInt(br.readLine()));
		}

		for (int i = 1; i < n; i++) {
			subList.add(Math.abs(list.get(i) - list.get(i - 1)));
		}

		int result = subList.stream()
			.reduce(Prob2981_5::gcd)
			.get();

		StringBuilder stringBuilder = new StringBuilder();

		for (int i = 2; i <= result; i++) {
			if (result % i == 0) {
				stringBuilder.append(i).append(" ");
			}
		}

		System.out.println(stringBuilder);
	}

	private static int gcd(int a, int b) {
		while (b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}