백준 - 수 묶기 ( 1744번, JAVA )

Greedy ( https://www.acmicpc.net/problem/1744 )

풀이

• 양수는 오름차순 우선순위큐 / 음수는 내림차순 우선순위큐 선언
• 둘 다 a와b로 짝을 지어서 곱했을때와 더했을 때를 비교해서 sum에 더해줬다.
• 또 둘 다 남은 수들에 대해서 비교를 해줘야하기 때문에 리스트 선언해서 남은 값들에 대해서도 비교해서 sum에 더하기

package problem_solving.greedy;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Stack;

public class BaekJoon_1744 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		PriorityQueue<Integer> plus = new PriorityQueue<>(Collections.reverseOrder());
		PriorityQueue<Integer> minus = new PriorityQueue<>();
		
		
		int sum = 0 ;
		ArrayList<Integer> list = new ArrayList<>();
		for(int i= 0 ; i < n ; i++) {
			
			int num = Integer.parseInt(sc.next());
			if( num > 0 ) {
				plus.offer(num);
			} else {
				minus.offer(num);
			}
		}
		
		while(plus.size() > 1 ) {
			int a = plus.poll();
			int b = plus.poll();
			
			if( a*b > a+b) {
				sum+=a*b;
			} else {
				sum+=a+b;
			}
		}

		
		while(!plus.isEmpty()) {
			list.add(plus.poll());
		}
		
		while(minus.size() > 1 ) {
			int a = minus.poll();
			int b = minus.poll();
			
			if( a*b > a+b) {
				sum+=a*b;
			} else {
				sum+=a+b;
			}
		}
			
		while(!minus.isEmpty()) {
			list.add(minus.poll());
		}
		
		if( list.size() == 2 ) {
			int a = list.get(0);
			int b = list.get(1);
			
			if( a*b > a+b) {
				sum+=a*b;
			} else {
				sum+=a+b;
			}
		} else if( list.size() == 1 ) {
			sum+= list.get(0);
		}
	
		System.out.println(sum);
	}

}