[백준 - 28703번] Double It - Java

문제

티어: 골드 3
알고리즘: 그리디

양의 정수로 이루어진 길이가
$N$인 배열
$A_1, \cdots, A_N$이 주어집니다. 당신은 원하는 만큼 다음 조작을 할 수 있습니다.

• 배열에서 원하는 수 하나를 골라서 $2$를 곱합니다.

조작 이후
$A_1, \cdots, A_N$의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요.

입력

첫 줄에 배열의 길이
$N$이 주어집니다.
$(1 \le N \le 200\,000)$ 

둘째 줄에
$N$개의 양의 정수
$A_1, A_2, \cdots, A_N$이 주어집니다.
$(1 \le A_i \le 10^9)$ 

출력

조작 이후
$A_1, \cdots, A_N$의 최댓값과 최솟값의 차이로 가능한 최솟값을 구하세요.

풀이

원하는 만큼 조작을 해서 최댓값과 최솟값의 차이를 최소화해야 한다.

어떻게 해야 할까?
바로든 생각은 최솟값을 최댓값 근처로 올리는 것이다.
그런데 근처라는게 너무 추상적이다. 그래서 좌표로 그려가면서 아이디어를 생각해 낼 수 있었다.

내가 푼 방법은 다음과 같다.

먼저, 최댓값이 아닌 모든 값들을 최대값을 넘지 않는 선에서 x2 조작을 최대로 적용해 줬다.

그러면 최댓값은 그대로고, 나머지 값들은 x2를 하면 최댓값이 바뀌는 위치에 존재한다.

그래서 가장 작은 값부터 반복을 시작하고, 답이 될 수 있는 값을 비교하며 answer를 업데이트해 준다.

answer = Math.min(result, Math.min(현재 최댓값 - 가장 작은 값, 가장 작은 값 x 2 - 그 다음 작은 값));

이를 언제까지 반복하는지가 중요하다.

N-1번 반복하면 된다. 즉, 가장 처음에 최댓값을 제외하고 나머지만 비교하면 되는 것이다.

왜냐하면 최댓값 x2를 하게되면 그 구조가 처음과 같아지게 되는데(가장 처음 최댓값과 x2를 하면 최댓값을 넘어가는 수들로 세팅된 구조) 이때는 차이가 더 벌어진 상태이기 때문에 최선의 선택이 아니다. 이는 직접 그려봐야 쉽게 이해할 수 있다.

예를 들면 8, 10있다고 했을 때 현재 차이는 2이다. 이때 x2를 적용해 주면 16, 20이고, 차이는 4가 된다. 그러니까 최초의 상태가 최선인 것이고, 이후 x2를 어떻게 적용하든 그 차이는 벌어진다.

시간 복잡도는 정렬을 하기 때문에 O(N * logN)이다.

소스 코드

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

public class Main {
    static int N;
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        int maxV = -1;
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            maxV = Math.max(maxV, A[i]);
        }
        if(N == 1) {
            System.out.println(0);
        } else {
            System.out.println(answer(A, maxV));
        }
    }
    
    static int answer(int[] A, int maxV) {
        int result = Integer.MAX_VALUE;
        for(int i=0; i<N; i++) {
            A[i] = init(A[i], maxV);
        }
        Arrays.sort(A);
        int max = A[N - 1];
        for(int i=0; i<N - 1; i++) {
            result = Math.min(result, Math.min(max - A[i], A[i] * 2 - A[i + 1]));
            max = A[i] * 2;
        }
        return result;
    }
    
    static int init(int v, int max) {
        while(v <= max) {
            v *= 2;
        }
        return v/2;
    }
}