[BOJ] 1744. 수 묶기

그리디 하게 접근하여 풀수있는 문제였다.

처음엔 문제를 간단하게 생각하여 내림차순으로 정렬후 두개씩 묶는 방법으로 접근하였는데, 잘 생각해보니 음수에 대해선 오름차순으로 처리하는게 최대값을 출력할 수 있는 것을 알게되었다. 따라서 음수, 양수에 대한 pq를 따로 나누었고, 각 각의 pq에 대해서 2개씩 묶는 방식으로 처리해주었다. 또, 0에 대해서 음수가 홀수개수인경우에 대해서도 예외처리를 해주어야한다.

package study5;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_bj_1744_수묶기 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(br.readLine());
        
        PriorityQueue<Integer> pq1 = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> pq2 = new PriorityQueue<>();
        
        boolean zero=false;
        
        for(int i=0;i<N;i++) {
            int num=Integer.parseInt(br.readLine());
            if(num>0) {
                pq1.add(num);
            }else if(num<0) {
                pq2.add(num);
            }else {
                zero=true;
            }
                
        }
        
        long sum=0;
        while(true) {
            if(pq1.size()==0 || pq1.size()==1) {
                break;
            }else {
                long num1=pq1.poll();
                long num2=pq1.poll();
                if(num2==1) {
                    sum+=(num1+num2);
                }else {
                    sum+=(num1*num2);    
                }
            }
        }
        
        while(true) {
            if(pq2.size()==0 || pq2.size()==1) {
                break;
            }else {
                long num1=pq2.poll();
                long num2=pq2.poll();
                
                sum+=(num1*num2);    
            }
        }
        
        if(pq1.size()==1) {
            sum+=pq1.poll();
        }
            
        if(pq2.size()==1) {
            if(zero!=true) {
                sum+=pq2.poll();
            }
        }
        
        
        System.out.println(sum);
    }
}