[백준] 수 묶기(1744)

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

특정 수열이 주어지면 특정 수를 적절히 묶어서 최댓값을 만들어 내야 한다.

예를 들어 A = [-1, -2, 0, 1, 2, 3, 4]가 주어지면, $(-2 × -1) + 0 + (1 × 2) + (3 × 4) = 16$이 되어야 한다는 것이다.

이를 해결하기 위해 양수 우선순위 큐, 음수 우선순위 큐, 0, 1 총 4가지 그룹으로 묶어서 관리해야한다.

먼저 양수 우선순위 큐는 내림차순으로 정렬하여 2개의 수를 뽑아 가장 높은 수끼리 서로 곱하면 된다.

다음으로 음수 우선순위 큐는 오름차순으로 정렬하여 2개의 수를 뽑아 절대값이 가장 큰 수끼리 서로 곱하면 된다.

여기서 주의해야할 부분이 나오는데, 음수가 홀수 개주어진 경우 음수가 1개 남을 것이다.

최댓값을 만들기 위해 아래와 같이 진행해야 한다.

if 0이 있는 경우
	마지막 음수와 0을 곱하여 0으로 만듦

else
	그냥 더해서 정답값을 업데이트

마지막으로 1이 몇개 있는지 카운트한 변수만 함께 더해주면 완성된다.

그래서 최종 소스코드는 아래와 같다.

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

public class P_1744 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> plus = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> minus = new PriorityQueue<>();
        int zero = 0;
        int one = 0;

        for (int i = 0; i < N; i++) {
            int input = Integer.parseInt(br.readLine());

            if (input == 0)
                zero++;

            else if (input == 1)
                one++;

            else if (input < 0) {
                minus.add(input);
            }
            else {
                plus.add(input);
            }
        }

        int answer = 0;
        while (plus.size() > 1) {
            int first = plus.poll();
            int second = plus.poll();

            answer += first * second;
        }

        if (!plus.isEmpty()) {
            answer += plus.poll();
        }

        while (minus.size() > 1) {
            int first = minus.poll();
            int second = minus.poll();

            answer += first * second;
        }

        if (!minus.isEmpty()) {
            if (zero < 1) {
                answer += minus.poll();
            }
        }

        answer += one;

        System.out.println(answer);
    }
}

크게 어렵진 않지만 많은 조건분기가 필요해 주의깊게 생각해볼 문제인 것 같다.