이번에 풀어본 문제는
백준 1744번 수 묶기 입니다.

📕 문제 링크

❗️코드

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

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());
        PriorityQueue<Integer> pos = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> neg = new PriorityQueue<>();

        for(int i = 0; i < n; ++i)
        {
            int input = Integer.parseInt(br.readLine());
            if(input > 0) pos.add(input);
            else neg.add(input);
        }

        int tmp = 0;
        int answer = 0;
        while(!pos.isEmpty())
        {
            tmp = pos.poll();
            if(!pos.isEmpty())
            {
                int next = pos.peek();
                tmp = (tmp * next) > tmp ? tmp * pos.poll() : tmp;
            }
            answer += tmp;
        }
        while(!neg.isEmpty())
        {
            tmp = neg.poll();
            if(!neg.isEmpty())
            {
                int next = neg.peek();
                tmp = (tmp * next) >= 0 ? tmp * neg.poll() : tmp;
            }
            answer += tmp;
        }
        System.out.print(answer);
    }
}

📝 풀이

입력된 N개의 수를 활용하여 두 수를 묶어서 곱하거나, 그대로 더하여 출력값을 최대로 만드는 문제입니다. 곱해서 더했을때 값을 증가시키려면 큰 값끼리 곱해야 하므로 우선 정렬이 필요하다고 생각했습니다. 하지만 음수는 오름차순으로 정렬해야 곱했을 때 값이 커지므로 양수와 음수를 나누어 우선순위 큐에 담아주었습니다.
양수먼저 정리하면, 다음 값이 1일 경우를 제외하고 묶어서 곱하는것이 클 수밖에 없으므로, 곱했을때 자기 자신보다 크다면 묶어주었습니다.
음수 큐는 0을 포함하게 하여 곱해서 0으로 음수를 상쇄시키거나, 곱셈을 활용해 양수로 바꿀 수 있을 경우 모두 묶어주도록 했습니다.
위의 과정을 모두 마치면 최댓값인 answer를 구할 수 있습니다.

📜 후기

쉬운 문제라고 생각했었지만, 생각보다 반례가 많아 몇번 틀렸던 문제입니다.
다양한 반례를 찾아내는 훈련도 필요할 것 같습니다.