[백준 | Java] 17087 숨바꼭질 6

내 풀이

수빈이의 위치 S에서 각 동생들의 위치까지 모두 도착할 수 있으려면 D값은 [S-각 동생들의 모든 위치]의 약수여야한다.
이처럼 공통되는 수 들의 최댓값을 구하는 문제는 최대공약수를 구하면 된다.

최대공약수는 유클리드 호제법을 사용해 구하였다.
유클리드 호제법에 대한 설명은 아래 포스팅에서 확인할 수 있다.

👉🏻 유클리드 호제법 설명 포스팅

처음엔 다음 알고리즘을 생각하여 코드를 작성했다.

1. Math.abs()를 사용해 [S-각 동생들의 모든 위치]를 절댓값으로 구하기
2. GCD 구하는 메소드 작성
3. 모든 D값을 겹치지 않도록 비교하며 GCD 메소드를 이용해 최대공약수들을 구하기
4. 구한 최대공약수들 중 Math.max()를 사용해 가장 큰 최대공약수를 출력

오답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        long all;
        long result = 0;
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.abs(Integer.parseInt(st.nextToken()) - S);
        }

        long first = arr[0];
        for (int i = 1; i < arr.length; i++) {
            all = gcd(first, arr[i]);
            result = Math.max(result, all);
        }
        System.out.println(result);
    }

    public static long gcd (long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a%b);
    }
}

결과는 오답이었고, 시간초과가 원인인듯 해 다른 풀이를 찾아보다가 내가 작성한 코드보다 효율적인 알고리즘이 있어 다시 작성하였다.

1. Math.abs()를 사용해 [S-각 동생들의 모든 위치]를 절댓값으로 구하기
2. GCD 구하는 메소드 작성 => 여기까진 내가 생각한 알고리즘과 일치
3. 모든 D값을 겹치지 않도록 비교하며 구한 최대공약수들의 최대를 반환 (❌, 비효율적)
   (➡️알고리즘 전환) 첫 번째 D, 두 번째 D의 최대공약수 A를 구한 후 A와 세 번째 D의 최대공약수 구하는 과정을 마지막 D까지 반복한 최종 값이 N개의 수의 최대공약수 (⭕, 효율적)

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int S = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Math.abs(Integer.parseInt(st.nextToken()) - S);
        }

        long result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result = gcd(result, arr[i]);
        }
        System.out.println(result);
    }

    public static long gcd (long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a%b);
    }
}