[백준]1744번 '수 묶기'(JAVA, 그리디)

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

 

 

[아이디어]

양수의 경우 가장 큰 수끼리, 음수의 경우 가장 작은 수 끼리 곱했을 때 제일 큰 값을 얻을 수 있다.

또한 0의 경우 묶지 못한 음수 하나를 없앨 수 있다.

 

따라서 양수는 가장 큰수부터 작은 수(내림차순)로, 음수와 0은 가장 작은 수부터 큰수(오름차순)로

우선순위 큐를 각각 만들어 저장한다.

그 후 큐의 제일 앞에 위치한 두 수를 묶어 곱한 후  answer에 더해준다.

 

*예외: 1의 경우 곱하는 것보다 더했을 때 더 큰 수가 된다. (ex) 1*2 < 1+2 ) 

 

import java.util.*;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

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> positive=new PriorityQueue<>(Collections.reverseOrder()); //양수를 내림차순 정렬하여 저장할 큐
        PriorityQueue<Integer> negativeNZero=new PriorityQueue<>(); //음수와 0을 오름차순 정렬하여 저장할 큐

        for(int i=0; i<N; i++){
            int num=Integer.parseInt(br.readLine());
            if(num>0) positive.offer(num);
            else negativeNZero.offer(num);
        }

        int answer=0;
        
        //양수 중에서 가장 큰 숫자끼리 곱하기. 
        while(!positive.isEmpty()){
            if(positive.size()==1) answer+=positive.poll(); //양수가 홀수 개인 경우
            else{
                int tmp= positive.poll();
                answer+=Math.max(tmp+positive.peek(),tmp*positive.peek()); //1이 나올 경우 곱하기가 의미가 없기 때문에 answer에 더하도록 함.
                positive.poll(); //묶인 수 제거
            }
        }
        
        /*음수 중에서 가장 작은 숫자끼리 곱하기(=양수). 
        0의 경우 큐에 저장된 음수들 중 가장 큰 음수와 묶어서 음수 하나를 없애버릴 수 있기 때문에
        음수를 저장하는 큐에 같이 저장한다.*/
        while(!negativeNZero.isEmpty()){
            if(negativeNZero.size()==1) answer+=negativeNZero.poll(); //음수가 홀수개인 경우
            else{
                int tmp=negativeNZero.poll();
                answer+=tmp*negativeNZero.peek();
                negativeNZero.poll(); //묶인 수 제거
            }
        }
        System.out.println(answer);

    }
}