[BJ] 1744 수 묶기 Java

백준 1744 수 묶기 

문제

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

1744번: 수 묶기

아이디어

• 양수*양수, 음수*음수 를 통해서 가장 큰 값을 도출 할 수 있다
• 물론 가장 큰 양수끼리의 곱, 그리고 가장 작은 음수 끼리의 곱이다
• 1의 경우 마지막에 더해주는 방식이 가장 큰 값을 만들 수 있다.
• 0은 음수가 총 홀수개 있다면 마지막으로 큰 음수에 곱해주면 되고 그렇지 않다면 나머지 음수는 그냥 더해주어야한다
• PriorityQueue를 사용해서 양수, 음수 큐 만들어주고 0과 1은 개수를 세어준다
• 양수의 경우 큐는 기본적으로 오름차순으로 우선순위를 두기 때문에 Collections.reverseOrder() 를 통해서 내림차순으로

코드

package baekjoon;
import java.util.*;

class BJ1744 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 수열에 양수, 음수, 1, 0 다 있음
        // 양수의 경우 큰 값 * 큰 값 해야 가장 큰 값
        // 음수는 서로 곱하면 양수가 되는 점에서 가장 작은값 * 가장 작은 값
        // 1은 곱하는 것보다 더하고, 0도 곱하는 것보다 더하는게 좋다
        // 기본적으로 오름차순이기에 역순으로
        PriorityQueue<Integer> plusPQ = new PriorityQueue<>(Collections.reverseOrder()); 
        PriorityQueue<Integer> minusPQ = new PriorityQueue<>();
        int zeroes = 0;
        int ones = 0;

        for (int i=0; i<n; i++) {
            int num = sc.nextInt();
            if (num == 1) ones++;
            if (num == 0) zeroes++;
            if (num > 1) plusPQ.offer(num);
            else minusPQ.offer(num);
        }

        // 각 큐 계산
        int answer = 0;
        while (plusPQ.size() > 1) {
            int a = plusPQ.poll();
            int b = plusPQ.poll();
            answer += a*b;
        }

        // 큐에 숫자가 남아있으면 그냥 더한다
        if (!plusPQ.isEmpty()) answer += plusPQ.poll();

        while (minusPQ.size() > 1) {
            int a = minusPQ.poll();
            int b = minusPQ.poll();
            answer += a*b;
        }

        // 음수가 남아있는데 0이 없으면 그대로 더 해줘야함
        // 0이 있으면 곱해주면 0이여서 최대값으로 나옴
        if (!minusPQ.isEmpty() && zeroes == 0) {
            answer += minusPQ.poll();
        }

        // 마지막에는 1의 개수를 더 함. 1이 1개면 1, 2개면 2... 라서 그대로 더함
        answer += ones;

        System.out.println(answer);
    }
}