[JAVA] 백준 1744 수 묶기_최소힙&최대힙

 

문제 : 

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

 

접근 : 

 

  - case 1 : 입력 받은 수 중 음수가 있는 경우, 작은 순서대로 2개 씩 묶어서 곱하면 최대치가 된다.

 

  - case 2 : 만약 0 이 있으면서 음수가 홀수 인 경우, 곱연산을 하면 0 이되므로 곱연산을 해준다.

 

  - case 3 : 입력 받은 수 중 양수가 있는 경우, 1보다 큰 경우에는 큰 수부터 2개씩 묶어서 곱하면 최대치가 된다.

 

  - case 4 : 1 이하의 수는 합 연산을 해서 최대치를 만든다.

 

 

 

 

코드 구현 : 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class Main {

    private final PriorityQueue<Integer> pq_plus;
    private final PriorityQueue<Integer> pq_minus;

    public Main(){
        pq_plus = new PriorityQueue<>(Comparator.reverseOrder());
        pq_minus = new PriorityQueue<>();
    }

    public void addUnit(int unit){
        if(unit > 0) pq_plus.add(unit);
        else pq_minus.add(unit);
    }
    public int run(){
        int ans = 0;

        while(pq_minus.size() > 1){
            ans += pq_minus.poll() * pq_minus.poll();
        }
        ans += pq_minus.isEmpty() ? 0 : pq_minus.poll();

        int a,b;
        while(pq_plus.size() > 1){
            a = pq_plus.poll();
            b = pq_plus.poll();
            if(a == 1 || b == 1) {
                ans += a + b;
                continue;
            }
            ans += a*b;
        }
        ans += pq_plus.isEmpty() ? 0 : pq_plus.poll();
        return ans;
    }

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

        for(int i = 0 ; i < t ; i++){
            m.addUnit(Integer.parseInt(br.readLine()));
        }
        System.out.println(m.run());
    }
}