[백준 1744] 수 묶기(Java)

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

이 문제는 그리디 알고리즘과 우선순위 큐를 사용하여 풀 수 있습니다. 이 문제는 양수일 경우와 음수일 경우 묶는 방법이 다르게 됩니다.

양수일 경우 : 절댓값이 큰 수들 순서대로 묶어서 더하기
--> 주의할 점 : 1과 어떤 수를 곱하면 손해이므로 둘 중 하나가 1일 경우 곱하지 않고 더하기

음수 및 0일 경우 : 절댓값이 큰 수들 순서대로 묶어서 더하기

따라서 우선순위 큐를 2개 설정하여 양수는 내림차순, 음수는 오름차순 정렬하여 값을 추가한 후 위의 규칙에 맞게 곱한 후 더해주면 됩니다.

다음은 코드입니다.

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

class Main{

    static int getSum(PriorityQueue<Integer> pq){
        Queue<Integer> queue = new LinkedList<>();
        while(!pq.isEmpty()){
            int curr = pq.poll();

            if(pq.isEmpty()) queue.add(curr);
            else{
                int next = pq.poll();
                if(curr==1 || next==1){
                    queue.add(curr);
                    queue.add(next);
                }
                else queue.add(curr*next);
            }
        }

        int res = 0;
        while(!queue.isEmpty()){
            res += queue.poll();
        }
        return res;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Integer> over = new PriorityQueue<>(Collections.reverseOrder());
        PriorityQueue<Integer> under = new PriorityQueue<>();

        int N = Integer.parseInt(br.readLine());
        for(int i=0;i<N;i++){
            int n = Integer.parseInt(br.readLine());
            if(n>0) over.add(n);
            else under.add(n);
        }

        int res = getSum(over) + getSum(under);
        System.out.println(res);
    }
}