백준 1744번 수 묶기 (JAVA)

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

1744번: 수 묶기

 

저는 음수와 양수에 대해 각각 우선순위 큐를 통해 문제를 해결하였습니다.

0은 음수의 우선순위 큐에 들어가도록 하였습니다. 이유는 -3 0 이렇게 남는다면 둘이 곱해야하지 최대가 되기 때문입니다. 양수의 경우는 곱하게 되면 0이 되기 때문에 최대가 되지 않습니다.

곱은 양수의 경우 큰 수 * 큰 수가 크고, 음수는 작은 수 * 작은 수가 더 크기 때문에 음수는 가장 값이 낮은 값이 먼저 나오게, 양수는 가장 값이 큰 값이 먼저 나오게 하여 2개의 곱을 더하고 하나만 남는다면 더하여 문제를 해결하였습니다.

양수에서 예외의 경우는 1인 경우는 두 수를 더하는 것이 더 크기 때문에 1인 경우는 그냥 더하여 문제를 해결하였습니다.

 

package BOJ.greedy;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.function.Function;

public class BOJ_1744 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        int n = stoi.apply(br.readLine());
        int[] arr = new int[n];
        for(int i = 0 ; i < n ; i++){
            arr[i] = stoi.apply(br.readLine());
        }
        PriorityQueue<Integer> plus = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minus = new PriorityQueue<>();
        for(int i = 0 ; i < n ; i++){
            if(arr[i] <= 0){
                minus.add(arr[i]);
            }else{
                plus.add(arr[i]);
            }
        }
        int result = 0;
        result += countMultiplySum(plus);
        result += countMultiplySum(minus);
        System.out.println(result);
    }

    private static int countMultiplySum(PriorityQueue<Integer> pq) {
        int sum = 0;
        while(pq.size() >= 2){
            int num1 = pq.poll();
            int num2 = pq.poll();
            if(num2 == 1){
                sum += num1 + num2;
                continue;
            }
            sum += num1 * num2;
        }
        while(!pq.isEmpty()){
            sum += pq.poll();
        }
        return sum;
    }
}