1. 문제 설명 📌

문제 링크

문제에서 수열이 주어지는데, 수열은 기본적으로 모두 더해진다. 하지만 만약 사용자가 임의의 수 2개를 골라서 괄호를 쳤을 경우, 해당 수는 곱해진다. 모든 수는 단 하나의 괄호에 포함되거나 아니면 괄호에 아예 포함되지 않는 2가지 선택지밖에 없다고 했을 때, 수열로 만들 수 있는 최대값을 구하라.

예를 들어 수열이 [0,1,2,4,3,5]로 주어졌을 때, 괄호가 없다면 합은 15이지만, 다음과 같이 괄호를 활용하면 0 + 1 + (2*3) + (4*5) 가 되면 값이 27로 최대가 된다.

2. 접근 방식 🗃️

KEYWORD: GREEDY ALGORITHM

(1) 경우의 수 생각하기

먼저 주어진 두 개의 수로 최대값을 만들 수 있는 경우는 무엇이 있을까?

두 수 모두 0보다 클 때: 이 경우 값 중 하나가 1이면 곱하는 것보다 차라리 더 하는 것이 값이 더 크다. 이를 감안하여 양수끼리의 계산 시에는 Math.max(o1+o2, o1*o2) 로 둘 중 최대값을 구하도록 한다.
두 수 모두 음수 일 때: 이 경우는 무조건 둘을 곱해서 양수로 만들어야 최대값이다.
o1 = 0, o2 != 0 일 때, 이 경우는 o2가 양수이면 그냥 더하고, 음수이면 곱해서 0으로 만드는 게 차라리 낫다.

이러한 경우를 생각해 문제를 푼다. 문제의 keypoint는 0의 존재 여부에 따른 예외처리이다. 두개씩 꺼내서 계산하다가, 음수가 1개 남았을 경우, 0이 있으면 곱해서 사라지지만, 0이 없으면 그냥 누적값에 더해야한다.

(2) 풀이 설명

우선순위 큐 2개와 그냥 큐 1개를 만든다. 각각 양수용, 음수용, 0이 들어가는 자리이다. 양수용 우선순위큐는 내림차순으로 해놓는다.
양수용 우선순위큐가 빌 때까지 2가지 값을 꺼내서 계산 후 최대값을 누적값에 더한다. (큐가 하나 남았을 때는 그냥 누적값에 더하도록 예외처리)
음수용 우선순위큐가 1개 남을 때까지 2개씩 꺼내서 곱하고 누적값에 더한다.
만약 음수용 우선수위큐에 값이 남았다면 입력에 0이 존재하면 누적에 더하지 말고 (둘이 곱해서 0이 되므로), 0이 존재하지 않으면 누적값에 더한다.

3. 코드 소개 🔎

import java.io.*;
import java.util.*;

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> plus = new PriorityQueue<>((o1,o2) -> o2 - o1);
        PriorityQueue<Integer> minus = new PriorityQueue<>();
        ArrayDeque<Integer> forZero = new ArrayDeque<>();

        for(int i = 0; i < N; i++){
            int now = Integer.parseInt(br.readLine());
            if(now > 0) plus.add(now);
            if(now < 0) minus.add(now);
            if(now == 0) forZero.add(now);
        }
        int acc = 0;
        while(!plus.isEmpty()){
            if(plus.size() == 1){
                acc += plus.poll();
            }else {
                int o1 = plus.poll();
                int o2 = plus.poll();
                acc += Math.max(o1+o2, o1*o2);
            }
        }

        while (!minus.isEmpty()){
            if(minus.size() == 1) {
                forZero.add(minus.poll());
            }else {
                int o1 = minus.poll();
                int o2 = minus.poll();
                acc += o1*o2;
            }
        }

        while (!forZero.isEmpty()){
            if(forZero.size() == 1){
                acc += forZero.poll();
            }else {
                int o1 = forZero.poll();
                int o2 = forZero.poll();

                if(o1 == 0 && o2 == 0) break;
                acc += Math.max(o1+o2, o1*o2);
            }
        }
        System.out.println(acc);
    }
}

4. 배운 것들 🎯

음수가 홀수면 음수끼리 짝을 지은 뒤 무조건 하나가 남고 짝수면 나머지가 존재하지 않는다. 때문에 0은 큐를 따로 만들어서 관리할 필요가 없다. 왜냐하면 음수가 남는다면 1개만 남기 때문에 0은 딱 한 번만 사용되기 때문이다. 따라서 0이 하나 이상 존재하냐? 아니면 아예 존재하지 않냐 토글로 값을 기록 후 계산하는 게 더 효율적이다.
나는 이를 깨닫고 급하게 break 문을 만들어 효율을 생각했다.

                int o1 = forZero.poll();
                int o2 = forZero.poll();

                if(o1 == 0 && o2 == 0) break;
                acc += Math.max(o1+o2, o1*o2);

다음은 break문을 사용했을 때와 사용하지 않았을 때의 시간 차이다.