백준 1744번 : 수 묶기 java

이 문제는 두 수를 곱하여 더하는 것이 더 큰 수를 만들 수 있는지, 그냥 더하는 것이 더 큰 수를 만들 수 있을지를 판별하여 더 큰 수를 만들어내는 문제입니다.

이 문제를 풀기 위해서 저는 우선순위 큐를 이용하였습니다.

우선순위 큐에 입력받은 데이터들을 전부 넣은 후 데이터들을 2개씩 poll 하면서 두 수가 모두 음수이거나 0일 때는 곱하여 더하는 것이 더 큰 수를 만들 수 있으므로 그렇게 하였습니다.

그리고 양수일 경우 1이 섞여 있으면 두 수를 그냥 더하는 것이 이득이고 이외에는 곱하는 것이 이득이므로 이렇게 했습니다.

---

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());
        int sum = 0;

        Queue<Integer> q = new PriorityQueue<>();

        for(int i = 0; i<N; i++)
            q.offer(Integer.parseInt(br.readLine()));

        //음수들, 0처리
        while(!q.isEmpty()){
            int first = q.poll();

            if(first>0){
                q.offer(first);
                break;
            }
            if(q.isEmpty()){
                sum += first;
                break;
            }

            int second = q.poll();
            if(second>0){
                sum += first;
                q.offer(second);
                break;
            }

            sum += first * second;
        }

        //내림차순으로 큐를 정렬
        Queue<Integer> q2 = new PriorityQueue<>(Collections.reverseOrder());
        while(!q.isEmpty())
            q2.offer(q.poll());

        //양수인 노드들을 처리
        while(!q2.isEmpty()){
            int first = q2.poll();

            if(q2.isEmpty()){
                sum += first;
                break;
            }

            int second = q2.poll();

            if(second == 1)
                sum += first + second;
            else
                sum += first*second;
        }

        System.out.println(sum);
    }
}

중간에 내림차순으로 다시 정렬을 해준 이유는 양수가 2 4 5 6 7과 같이 남아있을 때 아래에서부터 곱하여 올라오면 가장 큰 수가 아니기 때문입니다.