[BOJ][Java] 1744번 수 묶기

문제 설명

 

문제 링크 : https://www.acmicpc.net/problem/1744

 

위의 문제는 주어진 수열에서 수끼리 묶거나(곱하거나) 또는 그냥 더해서 최대합을 구하는 문제입니다.

최댓값을 구하기 위해서는 양수에서는 가장 큰 값과 그다음으로 큰 값을 곱해서 더하는 게 좋지만 만약 해당 양수가 1일 경우에는

곱하지 않고 그냥 더하는 게 더 큰 값이 됩니다.

 

음수에서는 내림차순으로 정렬하여 가장 작은 값과 그다음 작은 값을 곱해 더해줘야 합니다.

양수와는 다르게 음수에서는 -1이라고 하더라도 무조건 음수와 곱해준 뒤 더해주는 게 더 큰 값을 더할 수 있습니다.

이때 만약 같은 음수에서 짝지을 수가 없을 경우 0이 있다면 0과 곱해주는 것이 더 큰 값을 더할 수 있게 됩니다.

 

따라서 

0보다 큰 양의 정수를 모은 plusList

0보다 작은 음의 정수를 모은 minusList

0을 모은 zeroStack을 이용하여 문제를 풀 수 있는 그리디 알고리즘 문제입니다.

 

package boj;

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

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

        int N = Integer.parseInt(br.readLine());

        long answer = 0;
        List<Integer> pL = new ArrayList<>();
        List<Integer> mL = new ArrayList<>();
        Stack<Integer> zS = new Stack<>();

        for(int i = 0; i < N; i++){
            int num = Integer.parseInt(br.readLine());
            if(num > 0) pL.add(num);
            else if (num == 0) zS.add(num);
            else mL.add(num);
        }

        Collections.sort(mL);
        Collections.sort(pL, Collections.reverseOrder());
        boolean[] pV = new boolean[pL.size()];
        boolean[] mV = new boolean[mL.size()];

        for(int i = 0; i < pL.size(); i++){
            if(!pV[i] && i < pL.size() - 1){
                long now = pL.get(i);
                long next = pL.get(i+1);
                pV[i] = true;
                pV[i+1] = true;
                if(now != 1 && next != 1) answer += (now * next);
                else answer += (now + next);
            }else if(!pV[i] && i == pL.size() - 1) {
                answer += pL.get(i);
            }
        }

        for(int i = 0; i < mL.size(); i++){
            if(!mV[i] && i < mL.size() - 1){
                long now = mL.get(i);
                long next = mL.get(i+1);
                mV[i] = true;
                mV[i+1] = true;
                answer += (now * next);
            }else if(!mV[i] && i == mL.size() - 1){
                if(!zS.isEmpty()){
                    zS.pop();
                }else{
                    answer += mL.get(i);
                }
            }
        }

        System.out.println(answer);

    }
}