SWEA 13549. 최대공약수 최대화

수열에서 하나만 자신 혹은 다른 숫자로 변경하여 최대공약수의 최댓값을 구하는 문제이다. 수열의 길이는 2 이상, 10^5 이하이다.

 

하나씩 바꾸고 최대공약수를 구하는 방식은 시간 초과가 발생하므로 최대공약수의 누적이 필요하다. 앞에서 누적, 뒤에서 누적하여 중간의 숫자중 하나의 숫자만 없을 때 바로 앞까지의 최대공약수와 바로 뒤까지의 최대공약수의 최대공약수를 구하면 원하는 숫자를 변경한 최대공약수를 구할 수 있게 된다. 이를 위해 앞에서 누적하기 위한  배열, 뒤에서 누적하기 위한 배열을 만들고 최대공약수를 누적하였다.

 

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

int[] board = new int[n];
for(int i=0; i<n; i++) board[i] = Integer.parseInt(st.nextToken());
int[] preGCD = new int[n];
int[] postGCD = new int[n];
            
preGCD[0] = board[0];
for(int i=1; i<n; i++) preGCD[i] = gcd(preGCD[i-1], board[i]);
postGCD[n-1] = board[n-1];
for(int i=n-2; i>=0; i--) postGCD[i] = gcd(postGCD[i+1], board[i]);
int max = 1;
max = Math.max(postGCD[1], max);
max = Math.max(preGCD[n-2], max);
for(int i=1; i<n-1; i++) max = Math.max(max, gcd(preGCD[i-1], postGCD[i+1]));
            
sb.append(max).append('\n');

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for(int tc=1; tc<=T; tc++) {
            sb.append('#').append(tc).append(' ');
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] board = new int[n];
            for(int i=0; i<n; i++) board[i] = Integer.parseInt(st.nextToken());
            int[] preGCD = new int[n];
            int[] postGCD = new int[n];
            
            preGCD[0] = board[0];
            for(int i=1; i<n; i++) preGCD[i] = gcd(preGCD[i-1], board[i]);
            postGCD[n-1] = board[n-1];
            for(int i=n-2; i>=0; i--) postGCD[i] = gcd(postGCD[i+1], board[i]);
            int max = 1;
            max = Math.max(postGCD[1], max);
            max = Math.max(preGCD[n-2], max);
            for(int i=1; i<n-1; i++) max = Math.max(max, gcd(preGCD[i-1], postGCD[i+1]));
            
            sb.append(max).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    private static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}