프로그래머스 (고급) 친척 수

- 문제설명
친척 수란, 어떤 N개의 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 모든 M들을 말합니다. N개의 수가 주어졌을 때, 가능한 모든 친척 수를 알아내는 프로그램을 만드세요.

- 입출력 예
입력 #1

3
10
25
5

입력 #2
5
12
16
64
108
72

- 입력값 설명
첫째 줄에 종이에 적은 수의 개수 N이 자연수로 주어집니다. (2 ≤ N ≤ 30)
다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어집니다. 이 수는 모두 1보다 크거나 같고, 10,000보다 작거나 같은 자연수입니다. 같은 수가 두 번 이상 주어지지 않습니다. 항상 M이 하나 이상 존재하는 경우만 입력으로 주어집니다.

출력 #1
1 5

출력 #2
1 2 4

- 출력값 설명
첫째 줄에 가능한 M을 공백으로 구분하여 모두 출력합니다. 이때, M은 증가하는 순서이어야 합니다.

 

 

- 풀이 과정

 

나머지가 모두 같기 위해 최대공약수를 활용해야 겠다는 생각이 들었습니다.

수식으로 나타낸다면 아래와 같습니다. 

 

성립해야 하는 것

 

최대 공약수는 어떤 두 개 이상의 자연수들이 있을 때, 두 수의 공통된 약수 중 가장 큰 수 입니다.

최대 공약수를 구하는 알고리즘에는 유클리드 알고리즘이 있습니다!

유클리드 알고리즘은 a와 b 두 수의 최대공약수는 b와 a%b의 최대공약수와 같다는 공식입니다.

이를 반복해가면서 두 정수를 작게 만들고 결국, a%b가 0이 되는 순간이 올 때 a의 값이 최대 공약수가 됩니다. 

 

 

문제에서는 나머지를 같게하는 모든 M을 찾으라고 했으니 최대 공약수의 약수도 포함이 되기 때문에 마지막으로, 최대공약수의 약수를 찾으면 완성입니다. (0으로 완전히 나누어 떨어지는 수)

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

public class Main {
    public static void main(String[] args) throws IOException { 
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] a = new int[N];
        
        for (int i = 0; i < N; i++) {
            a[i] = scanner.nextInt();
        }
        
        // 차이의 최대공약수 구하기
        Arrays.sort(a);
        int interval = Math.abs(a[1] - a[0]);
        for (int i = 2; i < N; i++) {
            interval = gcf(interval, Math.abs(a[i] - a[i - 1]));
        }
        
        ArrayList<Integer> list = new ArrayList<>(); // 정답
        for (int i = 1; i <= interval; i++) { //최대공약수의 약수(즉 나누어 떨어지는 수 찾기)
            if (interval % i == 0) {
                list.add(i);
            }
        }
        
        Collections.sort(list);
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }
        
        scanner.close();
    }
    
    public static int gcf(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b; 
            a = temp; 
        }
        return a;
    }
}

 

 

다른 스터디 부원분들께서는 약수를 구하는 부분에서 제곱근을 활용하여 푸는 방식을 활용하셨는데 이를 사용하면 더욱 빠르게 진행할 수 있었을 것 같았습니다.

for i in range(1, int(g**0.5) + 1): # 제곱근까지만 확인. 소수체크 체크 문제 풀 때 했던 기법.
    if g % i == 0:
        result.append(i)
        if i != g // i:  # i와 g//i가 다르면 둘 다 추가

 

모두 나누어 떨어지는 수를 찾는 다른 코드도 있었고 이렇게 좋은 코드도 있구나 생각이 들었습니다.

처음엔 min을 사용하셨지만 1,3,15를 넣어봤을 때 오류가 발생하였고 부원들과 논의를 해본 결과, max를 활용하여 오류를 해결하였습니다.

n = int(input())
L = []
for i in range(n):
    L.append(int(input()))
    
max_num = max(L)

for i in range(1, max_num+1):
    check = [x%i for x in L]
    if check.count(check[0]) == len(check):
        # print(check)
        print(i, end =' ')