[백준] 28703: Double It - JAVA

in Algorithm on 자료 구조

https://www.acmicpc.net/problem/28703

풀이

배열에서 수 하나를 골라 2를 곱하는 동작을 반복한다.

이렇게 동작하는 중에 배열의 최댓값과 최솟값의 차이를 구하는 문제이다.

처음 배열의 최댓값을 저장해놓고

작은 수부터 2를 곱하기 위해 우선순위큐에 수들을 넣었다.

처음 주어진 최댓값이 우선순위큐에서 나오기 전까지 숫자들을 뽑으면서 2를 곱하고 답을 갱신했다.

메모리: 114588KB

시간: 1284ms

언어: Java 11

코드

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

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

        int max = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if (num > max) {
                max = num;
            }
            pq.add(num);
        }

        int tmp = max;
        int ans = tmp - pq.peek();
        while (pq.peek() < max) {
            int min = pq.poll();
            ans = Math.min(tmp - min, ans);
            tmp = Math.max(max, min * 2);
            pq.add(min * 2);
        }

        System.out.println(Math.min(tmp - pq.peek(), ans));
    }

}