109. 2981(검문)

import java.util.*;
import java.io.*;

class Main{
	public static void main(String args[])throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		ArrayList<Integer> num = new ArrayList<>();
		HashSet<Integer> numSet = new HashSet<>();
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i< T; i++) {
			num.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(num);
		
		int numGCD = num.get(1) - num.get(0);
		
		for(int i = 2; i< T; i++) {
			numGCD = gcd(numGCD,num.get(i) - num.get(i-1));
		}
		
		for(int i =2; i < (int)Math.sqrt(numGCD)+1;i++) {
			if(numGCD % i ==0) {
				numSet.add(i);
				numSet.add(numGCD/i);
			}
		}
		numSet.add(numGCD);
		
		ArrayList<Integer> result = new ArrayList<>(numSet);
		Collections.sort(result);
		
		for(int val : result) {
			System.out.print(val + " ");
		}
	}
	
	public static int gcd(int x,int y) {
		// 유클리드 호제법
		while(y!=0) {
			int r = x%y;
			x = y;
			y = r;
		}
		return x;
	}
}

문제요약

수가 주어졌을 때 M으로 나눌 때 나머지가 동일한 경우의 M을 구하라. (상근아... 검문이나 제대로 받아;;) 

설명

최대 1,000,000,000이라는 어마어마한 숫자로 인해 시간초과가 발생할 확률이 높은 문제이다.

 

수의 형태는 A = B * C + R 이다.

예를들어 A가 19이면 19 = 5 * 3 + 4 이며 위의 문제 첫번째 예시인  6 , 34 , 38에 적용하면,

다음과 같다.

 

M으로 나누었을 때 두 값의 나머지는 동일하다는 조건으로 인해,

다음과 같은 식이 완성된다.

 

이때, (6-34) / M 의 M과 (34-38) / M 의 M의 M이 같다.

때문에 (6-34) 와 (34-38)의 공약수를 구하면된다. 즉, 28과 4의  최대공약수를 찾고 그 최대공약수의 약수를 구하면 된다.

 

이를 빠르게 두번째 입력에 적용해 보면 다음과 같다.

 

입력 => 5 17 23 14 83

 

for(int i = 0; i< T; i++) {
			num.add(Integer.parseInt(br.readLine()));
		}
		
		Collections.sort(num);

정렬을 통해 다음값 - 현재값을 하여 음수가 발생하지 않도록 할 것이다.

public static int gcd(int x,int y) {
		// 유클리드 호제법
		while(y!=0) {
			int r = x%y;
			x = y;
			y = r;
		}
		return x;
	}

유클리드 호제법을 사용하여 최대공약수를 구한다.

int numGCD = num.get(1) - num.get(0);
		
		for(int i = 2; i< T; i++) {
			numGCD = gcd(numGCD,num.get(i) - num.get(i-1));
		}

먼저 numGCD를 만들고 (만약 TestCase가 2개이면, 그게 바로 최대공약수가 된다.) , 최대공약수를 구해간다.

예들들어 

다음과 같이 진행되는 것이다.

for(int i =2; i < (int)Math.sqrt(numGCD)+1;i++) {
			if(numGCD % i ==0) {
				numSet.add(i);
				numSet.add(numGCD/i);
			}
		}
		numSet.add(numGCD);
		
		ArrayList<Integer> result = new ArrayList<>(numSet);
		Collections.sort(result);
		
		for(int val : result) {
			System.out.print(val + " ");
		}

수가 커지면 끝까지 반복문을 돌리기에는 시간이 많이 걸린다.

때문에 제곱근 이후부터는 나눠도 의미없다는 것을 이용하여 반복 횟수를 줄인다.

 

예를들어 10의 제곱근은 3.16이다.

4 이후 부터는 이미 앞에서 구한 값으로 약수를 구할 수 있고, 제곱근 약수가 없다면 이후에도 약수가 없다.

 

위 로직을 그림으로 설명하면 다음과 같다.

만약 나누는 수가 중복이 발생할 수도 있기 때문에 집합(set)에 값을 집어넣고 리스트로 바꾼 뒤 정렬을 통해 출력을 한 것 이다.