[그리디] 백준-1744 수 묶기 골드4 (Java)

백준-1744 : 수 묶기

 

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

1744번: 수 묶기

 

아이디어

• 1을 제외한 양수는 큰수끼리 곱하면 커진다.
• 1은 더 해준다.
• 음수 * 음수는 양수이고 작은 음수끼리 곱하면 커진다.

풀이

• 아래 조건에 따라 우선순위 큐에 넣어준다.
  • 1은 결과에 더해준다.
  • 1보다큰 값끼리 우선순위큐에 넣어준다.
  • 1보다 작은값 끼리 우선순위 큐에 넣어준다.
• 우선순위 큐에 2개 이상 존재할때 곱하여 결과에 더해주고 1개의 경우에는 꺼내서 더해준다.

 

코드 (java)

package Greedy;

import java.util.*;

public class Baejoon1744 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        PriorityQueue<Integer> plusHeap = new PriorityQueue<>();
        PriorityQueue<Integer> minusHeap = new PriorityQueue<>();
        int result = 0;

        for (int i = 0; i < n; i++) {
            int tempNum = sc.nextInt();
            if (tempNum == 1) {
                result++;
            } else if (tempNum > 0) {
                plusHeap.add(-tempNum); // 내림차순
            } else {
                minusHeap.add(tempNum); // 오름차순
            }
        }

        while (!plusHeap.isEmpty()) {
            int beforeNum = -plusHeap.poll();
            if (!plusHeap.isEmpty()) {
                int currentNum = -plusHeap.poll();
                result += beforeNum * currentNum;
            } else {
                result += beforeNum;
            }
        }

        while (!minusHeap.isEmpty()) {
            int beforeNum = minusHeap.poll();
            if (!minusHeap.isEmpty()) {
                int currentNum = minusHeap.poll();
                result += beforeNum * currentNum;
            } else {
                result += beforeNum;
            }
        }

        System.out.println(result);

    }


}